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.
InputThe 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.
OutputOutput 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.
Sample Input2
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 Output28284
6
Gramham_scan代碼如下：
#define?MAX?120
#define?eps?1e-8
#define?Z(x)?(((x)>0?(x):-(x))<eps)
using?namespace?std;
struct?P
{
????double?x,y;?????
}p1,p2;
P?point[MAX],choose[MAX];
double?xmult(P?p1,P?p2,P?p0)
{
????return?(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);?
}
bool?cmp(P?a,P?b)
{
????double?ret=xmult(a,b,p1);
????return?Z(ret)?(xmult(a,b,p2)>0?1:0):(ret>0?1:0);
}
void?Gramham(int?n,P*?p,int&?s,P*?ch)
{
????int?i,k=0;
????for?(p1=p2=p[0],i=1;i<n;p2.x+=p[i].x,p2.y+=p[i].y,i++)
????????if?(p1.y-p[i].y>eps||(Z(p1.y-p[i].y)&&p1.x>p[i].x))
????????????p1=p[k=i];
????????p2.x/=n,p2.y/=n;
????????p[k]=p[0],p[0]=p1;
????????sort(p+1,p+n,cmp);
????????for?(ch[0]=p[0],ch[1]=p[1],ch[2]=p[2],s=i=3;i<n;ch[s++]=p[i++])
????????????for?(;s>2&&xmult(ch[s-1],p[i],ch[s-2])<-eps;s--);
}
posted on 2009-02-28 17:45
KNIGHT 閱讀(145)
評(píng)論(0) 編輯 收藏 引用