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