Zadanie

James Bond si neuvedomil, že Január a Leden je ten istý mesiac a omylom si naplánoval dve misie na jeden deň. Jeho úlohou je sledovať Dr. No aj Le Chiffra, ktorí zase plánujú ako ovládnuť svet. Obaja sa budú v Pondelok, 05 Januára 2015 23:00:00 GMT vyskytovať v Londýne, kde bude každý na inom mieste kuť pikle a spriadať zákerné plány.

Chudák James Bond si teraz musí nájsť miesto, z ktorého by mohol sledovať oboch zločincov naraz.

Úloha

Popis Londýna si trocha zjednodušíme, predstavíme si ho ako dvojrozmerú plochu, na ktorej sa nachádza niekoľko nepriehľadných prekážok obdĺžnikového tvaru. Prekážky sa môžu dotýkať rohmi aj stranami, ale nemôžu sa prekrývať.

James Bond a obaja zločinci predstavujú jeden bod v rovine. James Bond stojaci v bode J vidí zločinca stojaceho v bode Z, pokiaľ na sa úsečka JZ nepretína so žiadnou prekážkou1.

Pokiaľ sa nejaké prekážky dotýkajú stranou alebo rohom, nedá sa medzi nimi vidieť, ale pokiaľ sa úsečka JZ dotýka rohu či strany prekážky, tak James zločinca vidí. Navyše James nemôže stáť vo vnútri žiadnej prekážky a nesmie stáť ani v spoločnom rohu dvoch prekážok, pokiaľ sa prekážky nedotýkajú stenami. James môže stáť na kraji prekážky. Na obrázku môžeme vidieť, že James stojaci v bode \(j\) vidí zločincov stojacich v bode \(z_1\) a \(z_2\) ale nevidí zločincov stojacich v \(z_3\) a \(z_4\).

Nájdite bod z ktorého sú viditeľní obaja zločinci.

Formát vstupu

Na prvých dvoch riadkoch vstupu sú celé čísla \(x_d, y_d, x_\ell, y_\ell\) udávajúce pozície zločincov. Dr. No je na pozícii \((x_d,y_d)\) a Le Chiffre na \((x_\ell,y_\ell)\).

Na treťom riadku je celé číslo \(n\), \(0\leq n\leq 10\), udávajúce počet prekážok.

Nasleduje \(n\) riadkov a na i-tom z nich sú štyri celé čísla \(x_{1i}, y_{1i}, x_{2i}, y_{2i}\) popisujúce jednu prekážku. Bod \(x_{1i}, y_{1i}\) je ľavý dolný roh a \(x_{2i}, y_{2i}\) je pravý horný roh \(i\)-tej prekážky. Všetky súradnice v absolútnej hodnote neprekročia \(100\).

Zločinci majú rôzne pozície, a nenachádzajú sa vo vnútri ani na okraji žiadnej prekážky.

Formát výstupu

Pokiaľ existuje miesto, z ktorého môže James Bond sledovať oboch zločincov, vypíšte na prvý riadok YES a na druhý nejakú možnú pozíciu Jamesa. (Pokiaľ je takých miest viacero, vypíšte ľubovoľnú z nich.)

Súradnice vypisujte s presnosťou aspoň \(10^{-6}.\)

Ak žiadnen bod v rovine nevyhovuje, vypíšte jeden riadok a na ňom reťazec NO.

Príklady

Naľavo je nákres prvého vstupu a napravo nákres druhého.

 

Input:

-2 0
2 0
2
-1 -1 0 1
1 1 2 3

Output:

YES
0.0 2.0

Input:

0 1
3 1
3
-1 -1 1 0
-1 2 1 3
1 -1 2 3

Output:

NO

  1. James Bond má vynikajúci zrak a pokročilé technické vybavenie, takže vidí ľubovoľne ďaleko. Cez budovu však vidieť nedokáže.↩

Ak v meste nie sú budovy, tak je riešenie ľahké, ďalej predpokladajme, že v meste je aspoň jedna budova.

Označme si body, v ktorých sú zločinci, \(A\), \(B\) a bod, v ktorom je James Bond, si označme \(C\). Potom dôležitá myšlienka celého riešenia spočíva v tom, že pokiaľ má úloha riešenie (t.j. existuje miesto, kam si môže James sadnúť), tak existuje aj také riešenie, že roh nejakej budovy leží na priamke \(AC\) a roh nejakej budovy leží na priamke \(BC\).

Pokiaľ napríklad na priamke \(AC\) nie je žiaden roh, tak vieme posunúť bod \(C\) aby sa priamka dotkla nejakého rohu, bez toho aby James prestal vidieť niektorého zločinca. Nakreslite si a uvidíte to.

Tým pádom vieme, že riešenie stačí hľadať medzi priesečníkmi priamok typu \(AV\) s priamkami typu \(BU\), kde \(U\) a \(V\) sú nejaké rohy budov. Priamok \(AV\) je najviac \(40\), \(BV\) tiež, takže priesečníkov je najviac \(1600\). Z každého takéhoto priesečníku skontrolujeme, či by z neho James videl oboch zločincov.

Ku kompletnému riešeniu nám ostávajú už len dve veci:

  • Rozmyslieť si príslušnú geometriu – ako nájsť priesečník dvoch priamok, ako zistiť či sa dve úsečky pretínajú, ako zistiť, či bod leží na priamke. Treba si tiež dávať pozor na nepresnosti pri počítaní s reálnymi číslami. Prekážky je najlepšie rozložiť na úsečky.

  • Vysporiadať sa s tým, že cez niektoré rohy sa dá vidieť a cez niektoré nie, že James nemôže sedieť vo vnútri budovy a niekedy ani v rohu. Spôsobov ako to vyriešiť je mnoho, napríklad sa dajú všetky prekážky o máličko zmenšiť, aby sa dalo vidieť okolo rohov a pozdĺž stien. Ak máme problém s nepresnosťami a je vidieť cez rohy prekážok, môžeme pridať budovám maličké vnútorné výstuže. Tiež do rohov, ktoré nemajú byť priesvitné, dáme maličké úsečky, ktoré zabránia pohľadu skrz. Na obrázkoch je vidieť znázornenie výstuží a úsečiek.

Celková časová zložitosť je \(O(n^3)\), kde \(n\) je počet prekážok v meste.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.