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
