Problem A
Avoiding the Abyss

Þessi mynd táknar sýnidæmi 1. Leiðin sem er tekin forðast laugina, en út frá gefnu upplýsingunum hefði hún getað skarast við laugina. Þannig lausnin í sýnidæminu var frekar heppin hér.

Þú stendur á punkti með heiltöluhnitin $(x_s, y_s)$. Þú vilt ganga til punktsins með heiltöluhnitin $(x_t, y_t)$. Til að gera það máttu ganga eftir runu af línustrikum. En það er sundlaug fyrir þér. Sundlaugin er rétthyrningur sem er hornréttur á ásana með neðra vinstra horn sitt á punktinum $(x_l, y_l$ og efra hægra horn sitt á punktinum $(x_r, y_r)$. Þú getur aldrei farið í gegnum sundlaugina, ekki einu sinni kantinn. Það er hins vegar mjög dimmt og þú veist hvorki hnitin $(x_l, y_l)$ né $(x_r, y_r)$. Í staðinn hentirðu stein í laugina sem uppljóstraði fyrir þér að punkturinn $(x_p, y_p)$ væri í lauginni eða á kanti laugarinnar.

Finndu leið til að ganga frá upphafspunkti til endapunkts meðfram runu línustrika þannig að þú farir aldrei í sundlaugina.

Inntak

Fyrsta línan inniheldur tvær heiltölur $x_s$ og $y_s$ ($-10^4 \leq x_s, y_s \leq 10^4$).

Önnur línan inniheldur tvær heiltölur $x_t$ og $y_t$ ($-10^4 \leq x_t, y_t \leq 10^4$).

Þriðja línan inniheldur tvær heiltölur $x_p$ og $y_p$ ($-10^4 \leq x_p, y_p \leq 10^4$).

Verkefnið er ekki aðlagandi, það er, fyrir sérhvert prufutilvik eru til fjórar heiltölur $x_l, y_l, x_r, y_r$ ($-10^4 \leq x_l < x_r \leq 10^4$, $-10^4 \leq y_l < y_r \leq 10^4$) sem tákna sundlaugina sem eru ákveðnar fyrirfram. Upphafspunkturinn og endapunkturinn eru alltaf stranglega utan sundlaugarinnar og punkturinn $(x_p, y_p)$ er í lauginni eða á kantinum. Upphafspunkturinn og endapunkturinn eru ávallt mismunandi. Athugið að dæmið er tæknilega séð gagnvirkt, svo það verður ekki EOF stafur aftast.

Úttak

Fyrst skaltu skrifa út eina heiltölu $N$ ($0 \leq N \leq 10$), sem táknar fjölda punkta milli upphafspunktsins og endapunktsins sem þú vilt heimsækja. Næst skaltu skrifa út $N$ línur, þar sem $i$-ta línan inniheldur tvær heiltölur $x_i, y_i$. Þessi hnit verða að uppfylla $-10^9 \leq x_i, y_i \leq 10^9$. Athugaðu að þetta eru ekki sömu skorður og eru á hinum hnitunum.

Þetta þýðir að þú munt ganga meðfram beinu línustrikunum milli $(x_s, y_s), (x_1, y_1), \dots , (x_N, y_N), (x_t, y_t)$ þar sem engin af línustrikunum skarast við sundlaugina. Hægt er að sýna fram á að lausn sé til í öllum tilfellum.

0 0
4 4
2 2

2
0 3
1 4