Fişierul intrare/ieşire:copaci.in, copaci.outSursăinfo-arena 1.0
AutorStefan GheorgheAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Copaci

Macarie, dupa ce a muncit o viata intreaga, se decide la batranete sa se retraga pe o insula pentru a-si gasi linistea interioara si a se dedica naturii. Astfel el cumpara o insula pe care cultiva pomi fructiferi. Insula poate fi reprezentata ca un poligon (nu neaparat convex) intr-un sistem de axe de coordonate pozitive. Pomii sunt plantati doar la coordonate naturale.

Cerinta

Macarie este interesat de numarul de copaci pe care il poate planta strict in interiorul insulei. In acest scop el va furnizeaza copacii care determina insula (varfurile poligonului).

Date de Intrare

Prima linie a fisierului copaci.in contine numarul intreg N de copaci de pe linie. Urmatoarele N linii contin cate doua numere intregi seperate prin cate un spatiu care descriu coordonatele celor N pomi date intr-o anumita ordine (trigonometrica sau orara).

Date de Iesire

Prima linie a fisierului copaci.out contine un numar care va reprezenta numarul de copaci strict in interiorul insula.

Restrictii si precizari

  • 3 ≤ N ≤ 100.000
  • Coordonatele copacilor au valori intregi din intervalul [0, 2.000.000]
  • pot fi dati mai mult de 2 copaci pe o latura a "poligonului" insulei (cum se vede si in exemplu, penultimul copac)

Exemplu

copaci.incopaci.out
13
3 1
6 3
9 2
8 4
9 6
9 9
8 9
6 5
5 8
4 4
3 5
2 4
1 3
21
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content