Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2010-06-21 09:59:48.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:cadrane.in, cadrane.outSursăStelele Informaticii 2010
AutorAndrei Paul PuniAdăugată decrawlerPuni Andrei Paul crawler
Timp execuţie pe test0.65 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cadrane

Qwerty a găsit un set de N puncte în vechea lui cutie cu jucării. Chewbacca aflând de acest set de puncte îl provoacă pe Qwerty la un joc cu cadrane. În acest joc primul jucător alege unul din cele N puncte şi trasează o dreaptă verticală care trece prin acel punct, iar al doilea jucător alege şi el unul din cele N puncte şi trasează o dreaptă orizontală care trece prin acel punct. Cele două drepte formează patru cadrane asemănător axelor de coordonate. Primul jucător primeşte câte un punct pentru fiecare punct afla în cadranul NE sau în cadranul SV, al doilea jucător primeşte câte un punct pentru fiecare punct care se află în cadranul NV sau în cadranul SE.

Qwerty va face prima mutare, el vrea să aleagă un punct astfel încât punctajul lui minim posibil să fie maxim.

Ajutăl pe Qwerty să afle punctajul maxim pe care îl poate obţine.

Date de intrare

Fişierul de intrare cadrane.in contine pe prima linie un singur numarl natural N reprezentand numarul de puncte din setul gasit de Qwerty. Pe urmatoarele N linii se vor afla doua numere intregi reprezentand
coordonatele punctelor.

Date de ieşire

În fişierul de ieşire cadrane.out se va scrie un singur numar reprezentand punctajul maxim pe care il poate obtine Qwerty.

Restricţii

  • 1 ≤ N ≤ 100 000

Exemplu

cadrane.incadrane.out
10
5 -1
2 4
-4 -3
-2 2
1 -5
4 -1
-1 3
-3 4
-3 -5
-4 4
5

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?