Fișierul intrare/ieșire	puncte.in, puncte.out	Sursă	OJI 2013 clasa a 8-a
Autor	Ana Întuneric	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	2 sec	Limită de memorie	32768 KB
Scorul tău	N/A	Dificultate	3

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Puncte (clasa a 8-a)

Andrei se descurcă foarte bine la geometrie și de aceea născocește tot felul de jocuri pe care le testează cu Alexandru, colegul său de bancă. Pentru a pregăti noul joc cu trei niveluri, Andrei desenează pe o foaie de matematică reperul cartezian xOy și mai multe puncte distincte. Fiecare punct desenat are atât abscisa x, cât și ordonata y, numere întregi.

La primul nivel, Alexandru determină numărul maxim de puncte (dintre cele desenate) aflate pe una dintre axele sistemului cartezian sau pe o dreaptă paralelă cu una dintre cele două axe.

La al doilea nivel, Alexandru consideră toate punctele desenate a căror abscisă x și ordonată y verifică cel puțin una dintre relațiile x=y sau x+y=0 și apoi calculează câte drepte distincte trec prin cel puțin două dintre aceste puncte.

La al treilea nivel, Alexandru numără și șterge punctele din 3 în 3 (primul, al 4-lea, al 7-lea etc.), începând cu cel mai din stânga punct desenat și continuând către dreapta. Dacă două sau mai multe puncte au aceeași abscisă, el le numără pe acestea de jos în sus (începând de la punctul cu ordonata cea mai mică). Când a ajuns cu număratul la cel mai din dreapta punct continuă cu cel mai din stânga punct rămas.

Alexandru se oprește cu numărarea și ștergerea când rămâne un singur punct desenat pe foaie.

Cerință

Scrieți un program care citește numărul natural nenul N, apoi cele 2*N numere întregi ce reprezintă coordonatele celor N puncte și determină:

a) NRP, numărul maxim de puncte (dintre cele desenate) aflate pe una dintre axele sistemului cartezian sau pe o dreaptă paralelă cu una dintre cele două axe;
b) NRD, numărul de drepte distincte care trec prin cel puțin două dintre punctele desenate a căror abscisa x și ordonată y verifică cel puțin una dintre relațiile x=y sau x+y=0;
c) XP reprezentând abscisa punctului rămas pe foaie la sfârșitul celui de-al treilea nivel al jocului.

Date de intrare

Fișierul de intrare puncte.in conține pe prima linie numărul N de puncte, iar pe fiecare dintre următoarele N linii, câte două numere întregi, despărțite printr-un spațiu, reprezentând, în ordine, abscisa și ordonata unui punct din plan.

Date de ieșire

Fișierul de ieșire puncte.out va conține pe prima linie numărul natural NRP, pe a doua linie numărul natural NRD, iar pe a treia linie numărul întreg ce reprezintă coordonata XP.

Restricții

• 5 ≤ N ≤ 250000
• coordonatele punctelor sunt numere întregi ce au maximum 3 cifre;
• Se acordă 20 % din punctaj pentru rezolvarea corectă a punctului a), 20 % din punctaj pentru rezolvarea corectă a punctului b) și 60 % din punctaj pentru rezolvarea corectă a punctului c).

Exemple

puncte.in	puncte.out	Explicații
5 -1 5 0 0 2 2 -3 3 2 -2	2 4 -1	a) Sunt maximum 2 puncte aflate pe o dreaptă paralelă cu una dintre cele două axe sau pe axe     b) Sunt 4 drepte distincte care unesc cel puțin două dintre punctele (0,0), (2,2), (-3,3) și (2,-2)     c) Se șterg, în ordine, punctele de coordonate: (-3,3), (2,-2), (0,0), (2,2). Punctul rămas are coordonatele (-1,5)