Državno natjecanje iz informatike 2017 / Druga podskupina (3. i 4. razred) / Drugi dan natjecanja - 2. zadatak

Mirko izrađuje platformsku igru za mobilne uređaje. Nivo igre se sastoji od dasaka raspoređenih u prostoru — svaka daska je jedna horizontalna ili vertikalna dužina u standardnom koordinatnom sustavu. Krajevi dužine su različite točke s cjelobrojnim koordinatama (pa je duljina svake dužine barem jedan). Ako dvije daske sadrže zajedničku točku onda kažemo da se sijeku. Krajevi dužine također pripadaju dasci pa tako, primjerice, smatramo da se sijeku i dvije daske koje se samo dodiruju krajevima. Nivo je takav da se dvije horizontalne daske ili dvije vertikalne daske nikad ne sijeku.

Poziciju igrača u igri predstavljamo točkom u koordinatnom sustavu, a igrač u svakom trenutku mora biti na nekoj dasci. Igrač se može kretati duž dasaka, a ako se dvije daske sijeku on može u tom sjecištu preći s jedne daske na drugu.

Mirko je generirao nivo koji se sastoji od n dasaka te sada istražuje kako se igrač može kretati po nivou. Zadano je q upita gdje se svaki upit j sastoji od para točaka Aj i Bj koje obje leže na nekim daskama. Za svaki upit j, odredite je li moguće da igrač dođe iz pozicije Aj do pozicije Bj na opisani način.

Ulazni podaci

U prvom redu nalazi se prirodni broj n (1 ≤ n ≤ 200 000) — broj dasaka. U svakom od sljedećih n redova nalaze se četiri cijela broja x1, y1, x2, y2 (0 ≤ x1, y1, x2, y2 ≤ 200 000) — koordinate krajeva jedne daske. Svaka daska je ili horizontalna ili vertikalna dužina (vrijedi ili x1 = x2 ili y1 = y2). Niti jedne dvije horizontalne daske se ne sijeku. Niti jedne dvije vertikalne daske se ne sijeku. U sljedećem redu nalazi se prirodni broj q (1 ≤ q ≤ 200 000) – broj upita. U j-tom od sljedećih q redova nalaze se četiri cijela broja x1, y1, x2, y2 (0 ≤ x1, y1, x2, y2 ≤ 200 000) — koordinate točaka Aj i Bj. Za svaki pojedini upit j, točke Aj i Bj će biti različite te će obje ležati na nekoj dasci.

Izlazni podaci

Ispišite q redova. U j-ti red ispišite riječ “DA” ako je moguće doći od Aj do Bj odnosno riječ “NE” ako nije.

Bodovanje

• U test podacima vrijednim 15% bodova vrijedi n, q ≤ 1 000.

• U dodatnim test podacima vrijednim 50% bodova vrijedi da je ukupan različitih sjecišta najviše 200 000.

Probni primjeri

ulaz

6
2 0 2 5
6 0 6 6
0 4 7 4
0 1 3 1
4 1 7 1
3 2 5 2
2
0 1 6 2
3 4 4 2

izlaz

DA
NE

ulaz

8
1 1 3 1
1 1 1 3
3 1 3 3
1 3 3 3
2 2 5 2
1 5 6 5
6 5 6 1
6 1 4 1
5
2 3 5 2
1 2 5 1
2 5 5 1
5 1 5 5
5 1 4 2

izlaz

DA
NE
DA
DA
NE