Pe o foaie de matematică, tânărul Herostrate a desenat un sistem de coordonate cartezian cu centrul într-un punct de intersecţie a liniilor caroiajului, axele de coordonate fiind respectiv paralele cu laturile foii. Punctele de interesecţie ale liniilor caroiajului foii de matematică au coordonate întregi.
Pe foaia de matematică a fost construită din beţişoare o figură conexă. Au fost folosite beţişoare de două tipuri:
• De lungime 1 pentru elementele figurii plasate pe o latură verticală sau o latură orizontală a unui pătrăţel de pe foaie.
• De lungime sqrt(2) pentru elementele figurii plasate pe o diagonală a unui pătrăţel de pe foaie.
Tânărul Herostrate vrea să ardă figura. El poate să o aprindă în orice punct de coordonate întregi (de exemplu în punctul A (vezi desenul) figura nu poate fi aprinsă, dar în punctele B şi C – poate fi aprinsă).
Focul se răspândeşte de-a lungul fiecărui beţişor cu o viteză constantă (fiecare beţişor are viteză proprie de ardere). Beţişorul poate arde în câteva locuri (de exemplu când se aprinde din ambele capete; sau când la o intersecţie diagonală focul trece pe la un beţişor la altul – pe beţişorul nou aprins focul se extinde în ambele direcţii).
Cerinţă
Scrieţi un program, care va determina care este timpul minim în care poată să ardă complet figura.
Date de intrare
Fişierul de intrare bete.in conţine pe prima linie un număr natural n reprezentând numărul de beţişoare din care este construită figura. Pe următoarele n linii este descrisă figura, pentru fiecare beţişor din componenţa figurii fiind specificate pe o linie 5 numere întregi separate prin câte un spaţiu de forma X1 Y1 X2 Y2 T, unde X1, Y1, respectiv X2, Y2 reprezintă coordonatele extremităţilor beţişorului, iar T este timpul de ardere a beţişorului, dacă el este aprins la un singur capăt, timp exprimat în minute.
Date de ieşire
Fişierul bete.out va conţine o singură linie pe care va fi scris un număr real cu 4 zecimale, repezentând timpul minim de ardere a figurii exprimat în minute.
Restricţii
1≤n≤40
Se garantează că figura este conexă, toate beţişoarele au lungimea 1 sau sqrt(2) şi oricare două beţişoare nu coincid. -200≤X1, Y1, X2, Y2≤200; 0≤T≤107.
Foaia de matematică nu arde.
Rezultatul este considerat corect dacă diferenţa în valoare absolută dintre numărul din fişierul de ieşire şi soluţie nu depăşeşte 0.001.
igura se aprinde în punctul (0, 0).
Timp de 0,5 min. ard beţişoarele 1, 3 şi 4. După 0,5 min. se aprinde de la mijloc beţişorul 2 şi arde în ambele direcţii. După încă 0,5 min. ard total 1, 3, 4. Se aprinde beţişorul 5, care arde 1 min. (mai repede decât beţişorul 2).
Beţişorul 2 arde 0,5 min dinspre mijloc spre extremităţi. Se formează 2 fragmente, care ard câte 4,5 min. Dar, deoarece focul ajunge la ambele extremităţi, arderea are loc de 2 ori mai repede: 2,25 min. Total 1 + 2,25 = 3,25
3
1 1 1 2 10
1 2 2 2 10
1 1 2 2 50
35.0000
Figura se aprinde în punctul (1,2). Timp de 10 min ard beţişoarele (1 1, 1 2) şi (1 2, 2 2). Ultimul beţişor se aprinde concomitent din ambele capete şi arde în 25 min.
