Fișierul intrare/ieșire gps.in, gps.out Sursă ad-hoc
Autor Cătălin Frâncu Adăugată de avatar Catalin.Francu 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
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii