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.
BemenetA bemenet első sora a tesztesetek N (<= 100) számát tartalmazza. ezután N teszteset következik, mindegyik három sorból áll:
KimenetAz egyetlen sorba a legolcsóbb út költségét kell írni, legalább 10-6 pontossággal.
Példa
TesztadatokCímkékA feladat forrása: http://codeforces.com/problemset/problem/75/E
Algoritmusok: szakaszok metszéspontja, legrövidebb utak
|
Programozás > Feladatok >