凸包问题 我的一个凸包
求出凸包面积 然后加上2*PI*l
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int n_max=1005; const double PI=acos(-1.0); struct point { double x,y; void init(double tx,double ty) { x=tx; y=ty; } void operator = (const point &p) { x=p.x; y=p.y; } }p[n_max],ans[n_max]; bool bigger(point a,point b) { if(a.y==b.y) { return a.x<b.x; } return a.y<b.y; } bool smaller(point a,point b) { if(a.y==b.y) { return a.x>b.x; } return a.y>b.y; } double det(point a,point b,point c) { double x1=b.x-a.x; double y1=b.y-a.y; double x2=c.x-a.x; double y2=c.y-a.y; return x1*y2-x2*y1; } int Graham_scan(point *p,int n,point *ans) { int top=0; ans[top++]=p[0]; ans[top++]=p[1]; int i; for(i=2;i<n;i++) { while(top>1) { if(det(ans[top-2],ans[top-1],p[i])<0) { top--; } else { break; } } ans[top++]=p[i]; } return top; } int graham_scan(point *p,int n,point *ans) { sort(p,p+n,smaller); int t=Graham_scan(p,n,ans); sort(p,p+n,bigger); return t+Graham_scan(p,n,ans+t-1)-1; } double dist(point a,point b) { return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)); } int main() { int n,l; double x,y; while(~scanf("%d%d",&n,&l)) { int i; for(i=0;i<n;i++) { scanf("%lf%lf",&x,&y); p[i].init(x,y); } int nans=graham_scan(p,n,ans); double sum=0; for(i=1;i<nans;i++) { sum+=dist(ans[i],ans[i-1]); } sum+=2*l*PI; printf("%d\n",(int)(sum+0.5)); } return 0; }