poj 1113 求凸包

#include<cstdio> #include<cmath> #include<algorithm> #define N 1000 #define eps 1e-8 #define pi acos(-1.0) using namespace std; int n,L,top,pos=0; struct point { double x,y; }p[N],stack[N]; bool equal(double n) { return fabs(n-0)<eps; } double cross(const point p1,const point p2,const point p3) { return (p3.x-p1.x)*(p2.y-p1.y)-(p3.y-p1.y)*(p2.x-p1.x); } double dis(const point p1,const point p2) { return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)); } bool cmp(const point p1,const point p2) { double res=cross(p[0],p1,p2); if(equal(res)) return dis(p[0],p1)-dis(p[0],p2)<=0; else return res>0; } void solve() { int i; double res=0; for(i=1;i<n;i++) { if(p[pos].y>=p[i].y) { if(p[pos].y==p[i].y) { if(p[pos].x>p[i].x) pos=i; } else pos=i; } } point temp; temp=p[pos]; p[pos]=p[0]; p[0]=temp; sort(p+1,p+n,cmp); top=1; stack[0]=p[0]; stack[1]=p[1]; for(i=2;i<n;i++) { while(cross(stack[top-1],stack[top],p[i])<0) top--; stack[++top]=p[i]; } for(i=0;i<=top;i++) { res+=dis(stack[(i+1)%(top+1)],stack[i]); } printf("%.0lf\n",res+2*pi*L); return ; } int main() { int i; scanf("%d%d",&n,&L); for(i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); solve(); return 0; }