Programozás‎ > ‎Feladatok‎ > ‎

Legrövidebb út hajóval

Egy hajóval kell a legolcsóbb utat megtalálnunk két pont között. A tengeren kilométerenként egy pénzért evez a legénység. Út közben lehet egy sziget (ami egy konvex sokszög). Ha kell, a matrózok vállukra kapják a hajót és gyalog átviszik a szárazföldön, de ez nehezebb, így kilométerenként két pénz fizetendő.

Határozzuk meg a legolcsóbb út árát! 

Feladat

Írjunk programot, ami kiszámítja a legolcsóbb út költségét a kiindulási pont és a cél között.

Bemenet

A bemenet első sora a tesztesetek N (<= 100) számát tartalmazza. ezután N teszteset következik, mindegyik három sorból áll:
  • az első sorban először a kiindulási pont (sX, SY),  majd a cél (cX, cY) koordinátái találhatók (-100<= x,y <= 100)
  • a második sor a sziget csúcsainak M számát adja meg (3 <= M <= 30)
  • végül a harmadik sorban a sziget csúcsainak (x,y) koordinátáit kapjuk meg, az óramutató járásával ellentétes körüljárási irányban (szintén -100 és 100 közötti értékek)

Kimenet

Az egyetlen sorba a legolcsóbb út költségét kell írni, legalább 10-6 pontossággal.

Példa

Bemenet  Kimenet
2
1 7 6 7
4
4 2 4 12 3 12 3 2
-1 0 2 0
4
0 0 1 0 1 1 0 1
6.000000000
3.000000000

Tesztadatok

Címkék

Algoritmusok: szakaszok metszéspontja, legrövidebb utak