- UID
- 1
- 积分
- 15891
- 精华
- 贡献
-
- 威望
-
- 活跃度
-
- D豆
-
- 在线时间
- 小时
- 注册时间
- 2002-1-3
- 最后登录
- 1970-1-1
|
马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。
您需要 登录 才可以下载或查看,没有账号?立即注册
×
- #include <stdio.h>
- #include <math.h>
- #include <stdlib.h>
- typedef struct
- {
- double x;
- double y;
- }POINT;
- POINT result[102]; //保存凸包上的点
- POINT a[102];
- int n,top;
- double Distance(POINT p1,POINT p2) //两点间的距离
- {
- return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
- }
- double Multiply(POINT p1,POINT p2,POINT p3) //叉积
- {
- return ((p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x));
- }
- int Compare(const void *p1,const void *p2)
- {
- POINT *p3,*p4;
- double m;
- p3=(POINT *)p1;
- p4=(POINT *)p2;
- m=Multiply(a[0],*p3,*p4) ;
- if(m<0) return 1;
- else if(m==0&&(Distance(a[0],*p3)<Distance(a[0],*p4)))
- return 1;
- else return -1;
- }
- void Tubao()
- {
- int i;
- result[0].x=a[0].x;
- result[0].y=a[0].y;
- result[1].x=a[1].x;
- result[1].y=a[1].y;
- result[2].x=a[2].x;
- result[2].y=a[2].y;
- top=2;
- for(i=3;i<=n;i++)
- {
- while(Multiply(result[top-1],result[top],a)<=0)
- top--;
- result[top+1].x=a.x;
- result[top+1].y=a.y;
- top++;
- }
- }
- int main()
- {
- int i,p;
- double px,py,len,temp;
- while(scanf("%d",&n)!=EOF,n)
- {
- for(i=0;i<n;i++)
- scanf("%lf%lf",&a.x,&a.y);
- if(n==1)
- {
- printf("0.00\n");
- continue;
- }
- else if(n==2)
- {
- printf("%.2lf\n",Distance(a[0],a[1]));
- continue;
- }
- py=-1;
- for(i=0;i<n;i++)
- {
- if(py==-1 || a.y<py)
- {
- px=a.x;
- py=a.y;
- p=i;
- }
- else if(a.y==py && a.x<px)
- {
- px=a.x;
- py=a.y;
- p=i;
- }
- }
- //swap(a[0],a[p])
- temp=a[0].x;
- a[0].x=a[p].x;
- a[p].x=temp;
- temp=a[0].y;
- a[0].y=a[p].y;
- a[p].y=temp;
- qsort(&a[1],n-1,sizeof(double)*2,Compare);
- a[n].x=a[0].x;
- a[n].y=a[0].y;
- Tubao();
- len=0.0;
- for(i=0;i<top;i++)
- len=len+Distance(result,result[i+1]);
- printf("%.2lf\n",len);
- }
- return 0;
- }
|
|