ZOJ Problem Set - 3743
Alice's grandfather is a goatherd. One day, he asks Alice to help him shepherd a flock of lambs. But the lambs are very naughty and they run here and there. To look after the lambs better, Alice is going to use rope to circle them. But there are only a few stakes to fasten the rope. So Alice want you to help she caculate the minimal length of rope she is going to use. Suppose all the lambs stay there without moving when circling them.
It is guaranteed that all the lambs can be circled. If there is a rope cross a lamb, we think the lamb has not been circled.
There are multiple test cases. For each test case:
The first line contains two integers, N (3 <= N <= 100) and M (1 <= M <= 1000). N is the number of the stakes, M is the number of the lambs.
The next N lines contain the coordinate (SXi, SYi) of the stakes. The last M lines contain the coordinate (LXi, LYi) of the lambs. The absolute value of all integers in the input file will not exceeds 5000.
For each test case, output the minimal length of the rope. Any solution with a relative or absolute error of at most 1e-9 will be accepted.
4 1 0 0 2 2 0 2 2 0 1 1 4 1 0 0 1 2 2 0 0 2 1 1
Author: WANG, Yi
Contest: ZOJ Monthly, December 2013