posts - 74,  comments - 33,  trackbacks - 0
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.

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
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 阅读(130) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年1月>
28293031123
45678910
11121314151617
18192021222324
25262728293031
1234567

常用链接

留言簿(8)

随笔档案

文章档案

Friends

OJ

搜索

  •  

最新评论

阅读排行榜

评论排行榜