The 4th(2009) ACM Programming Contest of HUST - Onsite Contest

From: 2009-12-06 12:00:00 To: 2009-12-06 17:00:00 Now: 2017-09-20 01:08:38 Status: Public

E - LL and ErBao

Time Limit: 1s Memory Limit: 128MB

Submissions: 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