Programozás‎ > ‎Feladatok‎ > ‎

Fal

A mohó Király megbízta Főépítészét, hogy építsen falat a kastély köré. A Király annyira mohó volt, hogy nem fogadta el a Főépítész tervét, a tökéletes formájú téglafalat, tornyokkal, hanem azt parancsolta, hogy a lehető legolcsóbban készüljön el a fal, de azért nem mehet túl közel (egy adott távolságnál közelebb) a kastélyhoz.

Ha a Király úgy látja, hogy a Főépítész nem teljesítette maradéktalanul a parancsot, annak könnyen fejvesztés lehet a következménye.
Az egyetlen segítség, hogy a kastély alaprajza sokszög alakú, és a sokszög csúcsainak koordinátáit már az előző uralkodó alatt meghatározták, a birodalomban használt derékszögű koordináta-rendszerben. 

Feladat

Segítsünk a Főépítésznek, írjunk programot, ami kiszámolja a lehetséges legrövidebb fal hosszát, ami megfelel a feltételeknek.

Bemenet

A wall.in bemenet első sora az N és L egészeket tartalmazza. N (3 ≤ N ≤ 1000) a kastélyalaprajz csúcsainak száma, L (1 ≤ L ≤ 1000) pedig a megengedett minimális távolság a fal és a kastély között, méterben. A következő N sor a kastélyalaprajz csúcsainak koordinátáit adja meg, az óramutató járása szerinti körüljárási irányban. (-10000 ≤ Xi, Yi ≤ 10000) Minden csúcs különbözik, és a sokszög oldalai a csúcsokon kívül nem metszik egymást.

Kimenet

A wall.out kimeneti fájl egyetlen számot tartalmaz, a minimális szükséges falhossz értékét méterben megadva. A kerekítésnél figyeljünk arra, hogy fél méternél nagyobb pontatlanság a Főépítész fejébe kerülhet.

Példa

Bemenet  Kimenet
9 100
200 400
300 400
300 300
400 300
400 400
500 400
500 200
350 200
200 200
1628


Tesztadatok

Címkék

A feladat forrása: ???
Algoritmusok: geometriai algoritmus, konvex burok

megoldás