| Fişierul intrare/ieşire: | links.in, links.out | Sursă | ad-hoc |
| Autor | Adăugată de |  Cosmin-Mihai Tutunaru •stocarul | |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | links.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.
