Fişierul intrare/ieşire:pipe.in, pipe.outSursăLot Juniori 2008 - Baraj 4
AutorDana LicaAdăugată detoni2007Pripoae Teodor Anton toni2007
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Pipe

Gigel trebuie sa proiecteze instalatia de apa din propria curte. Curtea are dimensiuni infinite si nu este imprejmuita. El cunoaste coordonatele punctului in care se afla sursa de apa si coordonatele punctului unde va instala un robinet. Conducta trebuie proiectata astfel incat cele doua puncte sa fie unite. Pentru aceasta dispune de n tevi sub forma unor segmente ale caror lungimi se cunosc, dar care nu pot fi taiate. Doua tevi se vor conecta astfel incat unghiul dintre ele sa fie de 90°, 180° , 270° sau 360°, adica orice cuplare pe orizontala sau verticala(sus, jos, stanga, dreapta). Unele tevi sunt rosii iar altele sunt vopsite in albastru. Cele rosii se pot conecta doar pe verticala iar cele albastre doar pe orizontala. Pot exista tevi de aceeasi culoare si lungimi egale, dar fiecare teava se va folosi in instalatie o singura data.

Cerinta

Scrieti un program care sa determine lungimea minima de teava necesara pentru a uni cele doua puncte.

Date de intrare

Fisierul de intrare pipe.in are urmatorul format :

  • pe prima linie numarul n;
  • pe urmatoarea linie coordonatele carteziene ale sursei de apa xi yi, numere naturale separate printr-un spatiu;
  • pe urmatoarea linie coordonatele carteziene ale punctului unde va fi plasat robinetul xf yf,numere naturale separate printr-un spatiu;
  • pe urmatoarele n linii descrierea fiecarei tevi realizata astfel: caracterul A pentru culoarea albastru sau R pentru culoarea rosu, urmat de spatiu si apoi de un numar natural reprezentand lungimea tevii.

Date de iesire

Fisierul de iesire pipe.out va contine pe prima linie un numar reprezentand lungimea minima determinata sau cuvantul imposibil daca nu se poate realiza conectarea cu tevile disponibile.

Restrictii

  • 1 ≤ n ≤ 100
  • 1 ≤ lungimea fiecarei tevi ≤ 290
  • 0 ≤ xi, yi, xf, yf ≤ 32.000

Exemplu

pipe.inpipe.out
8
2 3
6 8
A 9
R 3
R 13
R 8
A 2
R 4
A 15
R 12
37

Explicatie

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content