LL and ErBao
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 18
Solved: 4
- Description
- When LL and ErBao were young, they liked jumping rubber-rope (Tiao Pi Jin) very much. They jumped every day happily. But one day HH came and brought away the peaceful days. HH sometimes threw stones to them, and sometimes pushed them down suddenly. Seeing ErBao crying sadly, LL got angry finally, and decided to give HH some color see see.
There were n trees on the ground (regarded as points), and LL planed to use his rubber-rope to wrap all the trees and form a big circle, then fooled HH into it and threw stones to him. Before finding out how to fool HH into the circle, LL wants to know how big the rubber-rope circle would be, say, the perimeter.
But LL found it difficult than expected, because their playing territory and the trees were in a bigger fence (a simple polygon with m vertices). So, the rubber-rope mustn’t be out of the fence either. It’s your turn to help LL find the perimeter of the circle.
Sample #1 Sample #2 - Input
- The input contains multiple cases terminated with EOF.
For each case, first line contains two integers: m, n.
(3 <= m <= 500, 0 <= n <= 500)
Next m lines each contain two integers: Xfi, Yfi ----coordinate of the fence’s ith vertex, in Counterclockwise order.
Next n lines each contain two integers: Xti, Yti ----coordinate of the ith tree.
It’s guaranteed that all trees were strictly in the fence, and the fence doesn’t intersect or touch itself.
The absolute value of the coordinates doesn’t exceed 10000.
- Output
- For each case output the perimeter of the rubber-band with three digits after the dot.
- sample input
-
8 2 0 0 30 0 30 20 20 20 20 10 10 10 10 20 0 20 5 15 25 15 12 5 5 5 5 20 -5 20 -5 5 -20 5 -20 -5 -5 -5 -5 -20 5 -20 5 -5 20 -5 20 5 0 0 0 17 0 -17 17 0 -17 0
- sample output
-
Case #1: 48.284 Case #2: 104.000
- hint
- source
- Xu Han, HUST Campus 2009