Fișierul intrare/ieșire	gps1.in, gps1.out	Sursă	ad-hoc
Autor	Cătălin Frâncu	Adăugată de	Spatarel Dan-Constantin • spatarel
Timp de execuție pe test	0.15 sec	Limită de memorie	512 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

GPS1

Un turist (electoral) are un gps1 cu N puncte de interes pe hartă. Turistul se întreabă: din cele 2^N 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, x_i y_i, 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 ≤ x_i, y_i ≤ 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.in	gps1.out	Imagine
5 2 2 6 6 7 1 11 3 5 8	26

Explicație

Din cele 2⁵ = 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.