K. Fish’s mission
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 21 Accepted Submission(s) : 6
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
Fish is the team leader of SHU-ACM, but you maybe don’t know, he’s also an excellent Water pipe workers of Shanghai University. One day, he got an mission from his boss.
There are many student canteens in Shanghai University, his mission is to find a right place to build a water station and lay water pipes between those canteens and the water station.
But the boss is as mean as Fish, he wants to save more money, which means the length of the water pipes should be as short as possible.
NOTE: AS LONG AS THE WATER ARRIVES ONE CANTEEN, WE ASSUME THE WATER OF PIPES WILL BE USED UP.
There are many student canteens in Shanghai University, his mission is to find a right place to build a water station and lay water pipes between those canteens and the water station.
But the boss is as mean as Fish, he wants to save more money, which means the length of the water pipes should be as short as possible.
NOTE: AS LONG AS THE WATER ARRIVES ONE CANTEEN, WE ASSUME THE WATER OF PIPES WILL BE USED UP.
Input
The first line of input contains a positive integer N <= 100, the number of canteens. N lines follow; each gives (x,y) coordinates (meter.) of each canteen. All coordinates are integers between 0 and 10,000.
Ensure all the canteens to form a convex polygon
Ensure all the canteens to form a convex polygon
Output
Output will consist of a single line containing the total length of the water pipes with three digits after the decimal point
Sample Input
4 0 0 0 10000 10000 10000 10000 0
Sample Output
28284.271
Author
Source
developing schools contest 5