Page 15 - MATINF Nr. 11-12

a
Concursul de Informatic˘ Programming Day 15

Cerint , a 2 ( 80 puncte)

Se determin˘a p = num˘arul de mas , ini cu anul de fabricat , ie x. Apoi, se foloses , te expresia
comb(p, 1)∗comb(n−p, k−1)+comb(p, 2)∗comb(n−p, k−2)+. . .+comb(p, p)∗comb(n−p, k−p)
s , i rezult˘a suma % 6869, folosind triunghiul lui Pascal.

Problema 2 – octogon

Cerint , e
Cunoscˆand coordonatele a n puncte ˆın plan astfel ˆıncˆat s˘ nu existe trei puncte coliniare, se
a
cere:

1. num˘arul de segmente cu ambele capete ˆın mult , imea dat˘a de puncte, care au dreptele
suport paralele cu una din axele de coordonate;
2. partea ˆıntreag˘a a ariei maxime a unui octogon cu toate vˆarfurile ˆın mult , imea dat˘a de
puncte.

Date de intrare

Pe prima linie a fis , ierului de intrare octogon.in se afl˘a C – cu valorile 1 sau 2, pe a doua
linie n, iar pe urm˘atoarele n linii se afl˘ perechi de numere naturale separate prin cˆate un spat , iu,
a
reprezentˆand abscisa s , i ordonata fiec˘arui punct.

Date de ies , ire
Dac˘a C este 1, fis , ierul de ies , ire octogon.out va cont , ine num˘arul de la cerint , a 1. Dac˘a C
este 2, fis , ierul de ies , ire octogon.out va cont , ine num˘arul de la cerint , a 2.

Restrict , ii s , i preciz˘ari

1. 8 ≤ n ≤ 18;
2. coordonatele punctelor sunt numere naturale ≤ 100000;
3. octogonul este un poligon convex cu 8 vˆarfuri.
a
4. Pentru rezolvarea corect˘ a cerint , ei 1 se vor acorda 20 de puncte.
5. Pentru rezolvarea corect˘a a cerint , ei 2 se vor acorda 80 de puncte.

Exemplu

octogon.in octogon.out
1 8
10
0 50
80 40
100 0
100 150
150 50
50 150
150 100
40 80
0 100
50 0