| Fişierul intrare/ieşire: | camp.in, camp.out | Sursă | ONI 2017, clasa a 10-a |
| Autor | Adrian Budau, Maria Pandele, Patrick Sava | Adăugată de |  Bogdan Ciobanu •bciobanu |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | camp.out | Explicaţ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. | 
|
