UVA 218

UVA 218"/>

UVA 218

凸包水题

求凸包   求边长

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define eps 1e-8
using namespace std;struct Point
{double x,y;Point (double x = 0,double y = 0):x(x),y(y){}
};typedef Point Vector;Vector operator -(Vector A,Vector B)
{return Vector(A.x-B.x,A.y-B.y);
}double Cross(Vector A, Vector B)
{return A.x*B.y -A.y*B.x;
}int cmp(Point a,Point b)
{if(a.x<b.x)return 1;else if(a.x == b.x && a.y < b.y)return 1;return 0;
}int ConvexHull(Point *s,int n,Point *ch)
{sort(s,s+n,cmp);int m = 0;for(int i = 0; i < n; i++){while(m >1 && Cross(ch[m-1]-ch[m-2],s[i]-ch[m-2])<= 0)m--;ch[m++] = s[i];}int k = m;for(int i = n-2; i >=0; i--){while(m > k && Cross(ch[m-1]-ch[m-2],s[i]-ch[m-2]) <= 0)m--;ch[m++] = s[i];}if(n>1)m--;return m;
}double Length(Point a,Point b)
{return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}int main()
{#ifdef LOCALfreopen("in.txt","r",stdin);#endif // LOCALint N;int T = 1;while(scanf("%d",&N) != EOF){if(N == 0)break;struct Point s[N],t[N];for(int  i = 0; i < N; i++)scanf("%lf%lf",&s[i].x,&s[i].y);int m = ConvexHull(s,N,t);printf("Region #%d:\n",T++);for(int  i = m; i >= 0 ;i--){printf("(%.1lf,%.1lf)",t[i].x,t[i].y);if(i > 0)printf("-");}printf("\n");double dis = 0;for(int i = 0; i < m; i++)dis += Length(t[i],t[(i+1)%m]);printf("Perimeter length = %.2lf\n\n",dis);}return 0;
}