7135번 - Tee 스페셜 저지다국어

Üks saar on jagatud $N$ maatükiks. Iga maatükk on ristküliku kujuga. Vaja on ehitada tee punktist $A$ punkti $B$ nii, et tee kulgeks mööda maatükkide servasid (sest keegi maaomanikest ei soovi, et tee tema maatüki mitmeks väiksemaks tükiks jagaks).

Kirjutada programm, mis leiab lühima nõuetekohase tee punktist $A$ punkti $B$.

Tekstifaili esimesel real on maatükkide arv $N$ ($1 \le N \le 1000$). Järgneval $N$ real on maatükke defineerivate ristkülikute alumise vasakpoolse ja ülemise parempoolse nurga koordinaadid $X_0$, $Y_0$, $X_1$, $Y_1$. Viimasel kahel real on punktide $A$ ja $B$ koordinaadid $X_A$, $Y_A$ ja $X_B$, $Y_B$. Kõik koordinaadid on mittenegatiivsed täisarvud, mille väärtus ei ületa $1\,000\,000$. On teada, et punktid $A$ ja $B$ on maatükkide servadel. Lisaks on teada, et kõik maatükid on ühel saarel, kuigi saarel võib olla ka järvi.

Tekstifaili esimesele reale väljastada leitud tee pikkus $L$. Järgnevatele ridadele väljastada leitud tee lõikude otspunktide koordinaadid $X$, $Y$. Kui leidub mitu sama teepikkusega lahendust, väljastada ainult üks neist.