Fişierul intrare/ieşire:camp.in, camp.outSursăONI 2017, clasa a 10-a
AutorAdrian Budau, Maria Pandele, Patrick SavaAdăugată debciobanuBogdan Ciobanu bciobanu
Timp execuţie pe test0.5 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Camp

Maria petrece ultimele zile din vacanţa de Crăciun la Braşov, în aprilie. Aceasta este atât de nerăbdătoare ca zăpada să se topească încât deja îşi imaginează cum se joacă într-un spaţiu verde, de forma unui
poligon cu N vârfuri. Maria, pasionată de matematică de altfel, reprezintă acest poligon în sistemul de coordonate carteziene. Aceasta este foarte curioasă câte puncte laticeale se află în interiorul poligonului, cât şi pe marginile acestuia. Un punct laticeal este un punct (x,y) cu proprietatea că x şi y sunt numere naturale. Considerând această problemă mult prea uşoară pentru nivelul ei, aceasta vrea să o complice, atribuindu-i fiecărui punct laticeal de forma (x,y) un cost egal cu suma coordonatelor sale, x+y. Acum, mulţumită de ceea ce a realizat, vă roagă să aflaţi care este suma costurilor punctelor laticeale aflate în interiorul şi pe marginile poligonului.

Cerinţă

Având un poligon cu N vârfuri date în ordine trigonometrică, vi se cere să aflaţi care este suma coordonatelor punctelor laticeale aflate în interiorul şi pe marginea acestuia.

Date de intrare

Fişierul de intrare camp.in conţine pe prima linie un număr natural N, reprezentând numărul de vârfuri ale poligonului. Următoarele N linii vor conţine exact câte două valori naturale separate prin câte un spaţiu, reprezentând vârfurile poligonului, date în ordine trigonometrică.

Date de ieşire

Fişierul de ieşire camp.out va conţine pe prima linie numărul natural cerut.

Restricţii

  • 3 ≤ N ≤ 100.000
  • Pentru orice punct (x,y) din fişierul de intrare se garantează faptul că 1 ≤ x, y ≤ 100.000
  • Se garantează faptul că poligonul din fişierul de intrare este convex.
  • Pentru teste în valoare de 25 de puncte N ≤ 50 şi x,y ≤ 100
  • Pentru teste în valoare de încă 25 de puncte N ≤ 500 şi x,y ≤ 1.000

Exemplu

camp.incamp.outExplicaţie
3
5 1
6 6
1 5
122
Suma costurilor celor 16 puncte laticeale care se află în interiorul sau pe
marginile triunghiului cu vârfurile în coordonatele (5,1), (6,6) şi (1,5) este 122.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?