Fișierul intrare/ieșire | gps.in, gps.out | Sursă | ad-hoc |
---|---|---|---|
Autor | Cătălin Frâncu | Adăugată de | Cătălin Frâncu • Catalin.Francu |
Timp de execuție pe test | 1.4 sec | Limită de memorie | 2048 KB |
Scorul tău | N/A | Dificultate | N/A |
Vezi soluțiile trimise | Statistici
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.