Fişierul intrare/ieşire:tri3.in, tri3.outSursăCEOI 2009
AutorMihai PatrascuAdăugată deandrei-alphaAndrei-Bogdan Antonescu andrei-alpha
Timp execuţie pe test0.675 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Tri3

Se dau K puncte cu coordonate numere întregi pozitive. De asemenea, se mai dau M triunghiuri, fiecare dintre ele având un vârf în origine iar celelalte două vârfuri la coordonate numere întregi pozitive.

Determinaţi pentru fiecare triunghi dacă are în interiorul său cel puţin unul din cele K puncte date.

Niciunul dintre cele K puncte nu se găseşte pe o latură a oricărui triunghi.

Date de intrare

Prima linie a fişierului de intrare tri3.in va conţine K şi M. Următoarele K linii conţin câte 2 numere întregi x şi y, separate printr-un spaţiu, reprezentând coordonatele punctelor. Următoarele M linii conţin câte 4 numere întregi pozitive, separate printr-un spaţiu, (x1, y1) şi (x2, y2), reprezentând celelalte 2 vârfuri ale triunghiului, exceptând pe cel din origine.

Date de ieşire

Fişierul de ieşire tri3.out conţine exact M linii. Linia k conţine caracterul Y dacă al k-lea triunghi (în ordinea dată în fişierul de intrare) conţine cel puţin un punct în interiorul său, sau N în caz contrar.

Restricţii şi precizări

  • 1 ≤ K, M ≤ 100 000
  • 1 ≤ coordonatele celor K puncte ≤ 109
  • 0 ≤ coordonatele vârfurilor triunghiurilor ≤ 109
  • Triunghiurile nu sunt degenerate (toate au aria diferită de 0).
  • În 50% din teste, toate triunghiurile au vârfurile în punctele cu coordonate x1 = 0 şi y2 = 0. Acest lucru înseamnă că două din laturile triunghiului se găsesc pe axele de coordonate.

Exemplu

tri3.intri3.outExplicaţie
4 3
1 2
1 3
5 1
5 3
1 4 3 3
2 2 4 1
4 4 6 3
Y
N
Y
4 2
1 2
1 3
5 1
4 3
0 2 1 0
0 3 5 0
N
Y
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content