<PREV Problem:
NEXT>
Solved by 44 users: dan, robotact, DD, tomek, wojtekt, MasterZerg, Ravent, murphy, mikleb, wintokk, dragonghy, marek.cygan, proglamer, mylady, Cheryl, andyzh1314, zmy, Rizvanov, lutyj, Moonlight, Wind_Love, shangjingbo, tourist, WsemirZ, Zhukov_Dmitry, pmnox, liulz, zloy_mipt, mazahaka, MIKseR, UdH-WiNGeR, defrager, DAV, Al.Cash, stasg7, EAA2008, ripatti, Dest, gchebanov, Irkhin, Madiyar_Tktl, KOHECJIOH, avg79, JohnJones_001.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Enclosing point with polygon

Time limit = 2 second(s)

There are N points A1, A2, .. ,AN and point B at a plain. Find polygon with vertices Ai of minimal peremiter that encloses point B The polygon sides should be less or equal to K.

Input Input has the following format:

N K
XB YB
X1 Y1
..

XN YN

3 ≤ N ≤ 100, 0 < K ≤ 30000,
|XB|, |YB|, |Xi|, |Yi| < 10000. All coordinates and K are given with 4 digits after point.

Output The perimeter length with accuracy 0.01.

Input#1
3 6.0000
1.0000 1.0000
0.0000 0.0000
0.0000 3.0000
4.0000 0.0000
Output#1
12.00

Author:
Voroztsov Artem,
I Moscow individual students programming contest, MIPT, 17 October 2004.
30 October 2004

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 210ms

SW soft NIX
ID = 23.20.166.68