Robot                        

Un robot punctiform se poate deplasa, în plan, în linie dreapta în orice directie. Robotul se gaseste într-o pozitie initiala S si trebuie sa ajunga într-o pozitie finala F, evitand coliziunile cu obstacolele existente în teren. Obstacolele sunt suprafete poligonale convexe, cu interioarele si frontierele disjuncte. Spunem ca robotul a intrat în coliziune cu un obstacol daca pozitia sa devine interioara obstacolului. Prin urmare, daca robotul se deplaseaza de-a lungul unui obstacol, nu intra în coliziune cu acesta.

Cerinta

Scrieti un program care sa determine cel mai scurt traseu pe care robotul îl poate urma de la pozitia sa initiala S la pozitia sa finala F, fara a intra în coliziune cu nici un obstacol.

Traseul va fi precizat prin succesiunea punctelor critice (punctul initial, punctele în care robotul îsi schimba directia si punctul final). Lungimea traseului este egala cu suma lungimilor segmentelor care îl compun.

Date de intrare:

Fisierul de intrare ROBOT.IN contine:

xS yS                                                                 –  coordonatele pozitiei initiale a robotului
xF yF                                                                 –  coordonatele pozitiei finale a robotului
n                                                                         –  numarul de obstacole
k1                                                                       – numarul de varfuri ale primului obstacol
x1 y1
x2 y2
...
xk1 yk1                                                              –  coordonatele varfurilor primului obstacol
k2                                                                       –  numarul de varfuri ale celui de-al doilea obstacol
x1 y1
x2 y2
...
xk2 yk2                                                              –  coordonatele varfurilor celui de-al doilea obstacol
...
kn                                                                       –  numarul de varfuri ale celui de-al n-lea obstacol
x1 y1
x2 y2
...
xkn ykn                                                              –  coordonatele varfurilor celui de-al n-lea obstacol

Date de iesire:

Fisierul de iesire ROBOT.OUT contine traseul robotului codificat ca o succesiune de puncte între care robotul se misca în linie dreapta:

nr                                                                       –  numarul de puncte de pe traseu
xS yS                                                                 –  coordonatele punctului initial
x1 y1                                                                 –  coordonatele primului punct critic de pe traseu
x2 y2                                                                 –  coordonatele celui de-al doilea punct critic de pe traseu
...
xF yF                                                                 –  coordonatele punctului final

Restrictii:

§      n numar natural, 0<=n<=50
§      k1+k2+...+kn<=200
§      xi, yi sunt numere reale,  |xi|, |yi|<=100000
§      punctele S si F nu se afla în interiorul nici unui obstacol
§       coordonatele se vor afisa în fisierul de iesire cu trei zecimale semnificative.

Exemplu:

ROBOT.IN

10 5
-10 –10
1
3
0 0
0 10
10.5 0

ROBOT.OUT
3
10 5
10.5 0
-10 –10

Observatie: Daca exista mai multe trasee de lungime minima, în fisierul de iesire se va obtine o singura solutie.

Timp maxim de executie: 1 secunda/test.