Fişierul intrare/ieşire:gps.in, gps.outSursăad-hoc
AutorCatalin FrancuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test1.4 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

GPS

Un turist (electoral) are un GPS cu N puncte de interes pe hartă. Turistul se întreabă: din cele 2N submulţimi de puncte, câte pot fi încadrate pe ecranul dreptunghiular al GPS-ului astfel încât pe ecran să apară doar acea submulţime şi niciun alt punct?

Date de intrare

Fişierul de intrare gps.in conţine pe prima linie numărul de puncte N. Pe următoarele N linii se află câte o pereche de coordonate naturale, xi yi, despărţite printr-un spaţiu.

Date de ieşire

În fişierul de ieşire gps.out se va tipări numărul de submulţimi distincte ce pot fi încadrate pe ecran, modulo 100.003.

Restricţii

  • 1 ≤ N ≤ 5.000
  • 1 ≤ xi, yi ≤ 1.000.000.000
  • nu există puncte coliniare pe orizontală sau pe verticală
  • un punct pe marginea sau în colţul ecranului este considerat prezent pe ecran
  • mulţimea vidă este o submulţime legală a setului de puncte
  • GPS-ul are zoom oricât de fin
  • GPS-ul are zoom diferit pe orizontală şi pe verticală, putând încadra dreptunghiuri cu orice raport lungime/lăţime
  • harta nu poate fi rotită

Exemplu

gps.ingps.outImagine
5
2 2
6 6
7 1
11 3
5 8
26

Explicaţie

Din cele 25 = 32 de submulţimi, 6 nu pot fi încadrate exclusiv: ACE, ACDE, ADE, CDE, CE, DE (toate ar conţine, obligatoriu, şi punctul B).

Observaţie

O versiune a acestei probleme cu limite mai mici de timp şi memorie găsiţi aici.

Trebuie sa te autentifici pentru a trimite solutii. Click aici