Gigel trebuie să proiecteze instalaţia de apă din propria curte. Curtea are dimensiuni infinite şi nu este împrejmuită. El cunoaşte coordonatele punctului în care se află sursa de apă şi coordonatele punctului unde va instala un robinet. Conducta trebuie proiectată astfel încât cele două puncte să fie unite. Pentru aceasta dispune de n ţevi sub forma unor segmente ale căror lungimi se cunosc, dar care nu pot fi tăiate. Două ţevi se vor conecta astfel încât unghiul dintre ele să fie de 90, 180 , 270 sau 360 grade, adică orice cuplare pe orizontală sau verticală(sus, jos, stânga, dreapta). Unele ţevi sunt roşii iar altele sunt vopsite în albastru. Cele roşii se pot conecta doar pe verticală iar cele albastre doar pe orizontală. Pot exista ţevi de aceeaşi culoare şi lungimi egale, dar fiecare ţeavă se va folosi în instalaţie o singură dată.
Cerinţă
Scrieţi un program care să determine lungimea minimă de ţeavă necesară pentru a uni cele două puncte.
Date de intrare
Fişierul pipe.in are următorul format :
- pe prima linie numărul n;
- pe următoarea linie coordonatele carteziene ale sursei de apă xi yi, numere naturale separate printr-un spaţiu;
- pe următoarea linie coordonatele carteziene ale punctului unde va fi plasat robinetul xf yf,numere naturale separate printr-un spaţiu;
- pe următoarele n linii descrierea fiecărei ţevi realizată astfel: caracterul A pentru culoarea albastru sau R pentru culoarea roşu, urmat de spaţiu şi apoi de un număr natural reprezentând lungimea ţevii.
Date de ieşire
Fişierul pipe.out va conţine pe prima linie un număr reprezentând lungimea minimă determinată sau cuvântul imposibil dacă nu se poate realiza conectarea cu ţevile disponibile.
