Fişierul intrare/ieşire:gps1.in, gps1.outSursăad-hoc
AutorCatalin FrancuAdăugată despatarelSpatarel Dan-Constantin spatarel
Timp execuţie pe test0.35 secLimită de memorie512 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

GPS1

Un turist (electoral) are un gps1 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 gps1-ului astfel încât pe ecran să apară doar acea submulţime şi niciun alt punct?

Date de intrare

Fişierul de intrare gps1.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 gps1.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
  • gps1-ul are zoom oricât de fin
  • gps1-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

gps1.ingps1.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 mari de timp şi memorie găsiţi aici.

Trebuie sa te autentifici pentru a trimite solutii. Click aici