Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2009-05-01 09:10:56.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:dsip.in, dsip.outSursăAlgoritmiada 2009, Runda Finala
AutorCosmin GheorgheAdăugată degcosminGheorghe Cosmin •gcosmin
Timp execuţie pe test0.75 secLimită de memorie128000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Dsip

In momentul in care trimiti o sursa, vei putea vedea scorul obtinut pe o parte din testele folosite la evaluare in monitor.

Karina are o foaie de matematica pe care este desenat un sistem de coordonate cartezian. Ea deseneaza N puncte la coordonate intregi si M drepte. Karina stie ca orice dreapta imparte planul in doua semiplane. Ea este curioasa cum impart dreptele punctele in doua parti. Astfel ea vrea sa stie cate puncte sunt de o parte a fiecarei drepte si cate puncte sunt de cealalta parte. Mai exact pentru fiecare dreapta defineste N1 si N2 numarul de puncte de o parte si respectiv de cealata parte a dreptei. Karina vrea sa afle min(N1, N2) si max(N1, N2). Daca un punct se afla exact pe dreapta nu se considera in nici o parte a dreptei (nu se ia in considerare).

Date de intrare

Fişierul de intrare dsip.in va contine pe prima linie numerele N si M reprezentand numarul de puncte din plan si respectiv numarul de drepte. Pe urmatoarele N linii se vor afla cate 2 numere intregi reprezentand coordonatele punctelor. Urmatoarele M linii vor contine cate 4 numere intregi x1, y1, x2 si y2 reprezentand doua puncte prin care trece dreapta respectiva.

Date de ieşire

Fişierul de ieşire dsip.out va contine M linii fiecare continand doua numere min(N1, N2) si max(N1, N2) reprezentand raspunsul pentru fiecare dreapta in parte in ordinea in care acestea apar in fisierul de intrare.

Restricţii

  • 1 ≤ N ≤ 2 000
  • 1 ≤ M ≤ 200 000
  • Oricare 3 puncte din cele N sunt necoliniare.
  • Toate coordonatele din fisierul de intrare vor fi cuprinse intre 0 si 10 000
  • Atentie: se recomanda evitarea folosirii tipurilor de date reale sau folosirea unei precizii de ordinul 10-11 sau chiar mai mica.
  • Din cauza unor posibile erori de precizie se garanteaza ca pentru 50% din teste toate coordonatele vor fi cuprinse intre 0 si 1 000

Exemplu

dsip.indsip.out
5 6
4 7
8 6
4 6
7 3
3 2
2 4 7 4
4 1 4 4
5 2 6 5
2 1 5 4
8 2 3 7
3 3 4 2
2 3
1 2
2 3
2 2
1 2
1 4
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?