| Fişierul intrare/ieşire: | gps.in, gps.out | Sursă | ad-hoc |
| Autor | Catalin Francu | Adăugată de |  Catalin Francu •Catalin.Francu |
| Timp execuţie pe test | 1.4 sec | Limită de memorie | 2048 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.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.in | gps.out | Imagine |
|---|---|---|
| 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.
