Watch out the Animal
Time Limit: 1000 ms
Memory Limit: 32768 KiB
Problem Description
There are n resting-places in the safari park. Some administrators are at the resting-places.Now we want to build a station in the park to guarantee that no animals run out of the park.Every two resting-places form a segment. If an animal runs accross a segment and thus will never be observed again, we say it is running out of the park. Lines of communication can be built between the station and a certain resting-place, but not between resting-places. Please calculate where the station should be built so that we will always know whether there are any animals running out of the park and at the same time minimize the length of the communication lines.
Input
The first line of input contains a positive integer, N(5<=N<=100), the number of resting-places.N lines follow. Each gives the (x,y) coordinates (in mm) of a resting-place within the park. All coordinates are integers between 0 and 10,000.
Output
Output consists of one number, the total distance, rounded to the nearest mm.
This problem contains multiple test cases!
The first line of a multiple input is an integer T, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.
The output format consists of T output blocks. There is a blank line between output blocks.
This problem contains multiple test cases!
The first line of a multiple input is an integer T, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.
The output format consists of T output blocks. There is a blank line between output blocks.
Sample Input
2 8 0 0 1453 6432 0 10000 9876 1234 10000 10000 8754 2345 10000 0 2465 6843 5 2 2 0 0 2 0 0 2 1 1
Sample Output
28284 6
Hint
hdoj2440 有链接提示的题目请先去链接处提交程序,AC后提交到SDUTOJ中,以便查询存档。
Source
2008 Asia Harbin Regional Contest Online