2511 - Cherhanale

Enunt

Pescar împătimit pe râul Olt și pe bălțile din lunca Dunării, Eric a ajuns în Deltă și acum și-a propus să pescuiască pe canalele de aici. Sejurul lui Eric în Deltă începe în ziua 0, atunci când el ajunge la cherhanaua din Tulcea. În fiecare din următoarele n zile pornește din cherhanaua în care se află, merge să pescuiască pe un canal și apoi depozitează peștele prins în altă cherhana (de unde va porni în ziua următoare). El și-a făcut de la început planul stabilind exact la care canal pescuiește în fiecare zi și la care cherhana depozitează peștele prins la finalul zilei respective. Dorește însă să meargă o distanță cât mai mică. Canalele sunt reprezentate prin drepte în plan iar cherhanalele prin puncte. În prima zi de pescuit, el pleacă de la cherhanaua din Tulcea (să o notăm cherhanaua 0), merge să pescuiască într-un loc din canalul 1, apoi depozitează peștele în cherhanaua 1. Rămâne aici peste noapte, apoi, în ziua 2, pornește din cherhanaua 1, pescuiește într-un loc (punct) de pe canalul 2 și depozitează peștele în cherhanaua 2 etc.

Cerinţa

Considerând că pescarul Eric se poate deplasa oricum dorește, determinați distanța minimă pe care o parcurge (suma lungimilor tuturor segmentelor pe care el le parcurge).

Date de intrare

Fișierul de intrare cherhanale.in conține pe prima linie valoarea n, reprezentând numărul de zile în care Eric pescuiește. Fiecare din următoarele n linii conțin câte 6 numere întregi, separate prin câte un spațiu: X1, Y1, X2, Y2, XC, YC. Punctele (X1,Y1) și (X2,Y2) determină dreapta suport a canalului iar punctul (XC,YC) reprezintă punctul ce indică o cherhana.

Date de ieșire

Fișierul de ieșire cherhanale.out va conține un număr real, ce reprezintă valoarea cerută.

Restricţii şi precizări

1 ≤ n ≤ 10; -100000 ≤ Xi, Yi, XC, YC ≤ 100000; punctul corespunzător cherhanalei din orașul Tulcea este (0,0); traversarea unui canal se consideră neglijabilă; canalele se continuă și de o parte și de alta a segmentului determinat de punctele date; pentru același canal, X1 ≠ X2 sau Y1 ≠ Y2; soluția se va afișa cu exact 5 zecimale, fără rotunjire, adică sub forma: parte intreaga(sol * 100000) / 100000.0; Pentru orice canal, atât cherhanaua imediat de dinainte de a se pescui în acesta cât și cea imediat de după pescuitul în acesta, nu se află pe acel canal.

Exemplu

cherhanale.in

1
5 1 1 5 3 0

cherhanale.out

6.70820

Rezolvare

<syntaxhighlight lang="python" line> import math

def read_input(filename):

   with open(filename, 'r') as file:
       n = int(file.readline().strip())
       data = [tuple(map(int, line.split())) for line in file.readlines()]
   return n, data

def distance(point1, point2):

   x1, y1 = point1
   x2, y2 = point2
   return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

def total_distance(n, data):

   total = 0
   for i in range(n - 1):
       point1 = data[i][4], data[i][5]  # Cherhana curentă
       point2 = data[i + 1][4], data[i + 1][5]  # Următoarea cherhana
       total += distance(point1, point2)
   return total

def write_output(filename, result):

   with open(filename, 'w') as file:
       file.write("{:.5f}\n".format(result))

def main():

   n, data = read_input('cherhanale.in')
   result = total_distance(n, data)
   write_output('cherhanale.out', result)

if __name__ == "__main__":

   main()

</syntaxhighlight>