ISUN1 - LL and ErBao

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.

Example

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

Output:
Case #1: 48.284
Case #2: 104.000


Added by:3xian
Date:2009-12-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Xu Han, HUST Campus 2009

hide comments
2009-12-27 09:52:28 Jakub Pachocki
@3xian

Ah, yes, I can see it now. I apologize for the hassle.
2009-12-27 09:26:24 3xian
@Jakub Pachocki
Your conjecture is wrong. The input data has no polygons in clockwise. Maybe there are some bugs in your program.
2009-12-27 07:18:58 Jakub Pachocki
Please verify that the input polygon is indeed in counterclockwise order - I get WA unless I check it and reverse the order of vertices in case it's clockwise.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.