== include(page="template/taskheader" task_id="links") ==
Poveste şi cerinţă...
Se dau $N$ puncte din plan prin coordonatele lor.
Se mai dau $Q$ perechi de puncte, diferite de cele date iniţial.
h2. 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.
h2. Date de intrare
Fişierul de intrare $links.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $links.out$ ...
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.
h2. 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$
h2. Exemplu
table(example). |_. links.in |_. links.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4 2
1 2
2 1
3 2
2 3
1 1 2 2
1 1 1 3
| 0
1
|
h3. 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.
== include(page="template/taskfooter" task_id="links") ==
