Fişierul intrare/ieşire:links.in, links.outSursăad-hoc
AutorAdăugată destocarulCosmin-Mihai Tutunaru stocarul
Timp execuţie pe test0.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Links

Se dau N puncte din plan prin coordonatele lor.
Se mai dau Q perechi de puncte, diferite de cele date iniţial.

Cerinţa

Să se verifice, pentru fiecare pereche de puncte (A , B) dintre cele Q, dacă există traseu care porneşte din A şi ajunge în B, prin deplasări cu paşi de lungime 1 spre Nord, Vest, Sud , Est şi evitând orice punct dintre cele N date iniţial.

Date de intrare

Pe primul rând al fişierului text links.in se află numerele naturale N şi Q, separate prin spaţiu. Pe următoarele N rânduri se află scrise câte două numere naturale, separate prin spaţiu, reprezentând coordonatele celor N puncte date. Pe următoarele Q rânduri se află scrise câte patru numere naturale, separate prin câte un spaţiu, reprezentând coordonatele celor Q perechi de puncte date pentru verificările cerute.

Date de ieşire

Pe fiecare din primele Q rânduri ale fişierului de ieşire links.out va fi scris unul dintre numerele 1 (adevărat) sau 0 (fals), reprezentând răspunsul la verificarea corespunzătoare, după cum există traseu sau nu există traseu între punctele din perechea dată în interogare.

Restricţii

  • 1 ≤ N ≤ 10^5
  • 1 ≤ Q ≤ 10
  • Coordonatele tuturor punctelor date sunt, numere naturale nenule mai mici decât 10^9
  • Pentru 30% din teste coordonatele tuturor punctelor date vor fi numere naturale nenule mai mici decât 10^3

Exemplu

links.inlinks.out
4 2
1 2
2 1
3 2
2 3
1 1 2 2
1 1 1 3
0
1

Explicaţie

La punctul (1,1) se poate ajunge doar trecând prin (2,3),(2,1),(1,2),(3,2) care sunt cele 4 puncte date şi deci trebuie evitate. Deci nu se poate ajunge de la (1,1) la (2,2).Răspunsul corect este 0.
De la (1,1) la (1,3) se poate ajunge pe traseul:(1,1),
(0,1), (0,2), (0,3), (1,3). Răspunsul corect este 1.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?