NézetNyomtat

Fal
Címkék > Feladat

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átarendszerben.

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 $\le$ N $\le$ 1000) a kastélyalaprajz csúcsainak száma, L (1 $\le$ L $\le$ 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 $\le {\tt X}_i, {\tt Y}_i \le$ 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

wall.in wall.out
9 100
200 400
300 400
300 300
400 300
400 400
500 400
500 200
350 200
200 200
1628

Tesztadatok