|
|
back to boardDiscussion of Problem 1185. WallPls explain me why WA ... I tried so many things ... // here is my code... #include <fstream.h> #include <math.h> #include <stdio.h> struct point { double x,y,ang; }; point a[1024],convex[1024],pom; double det (double x1,double y1,double x2,double y2,double x3,double y3) { return x1*(y2-y3)-y1*(x2-x3)+x2*y3-y2*x3; } void qsort (long l,long r) { double z; long i,j; i=l; j=r; z=a[(i+j)/2].ang; do { while (z>a[i].ang) i++; while (z<a[j].ang) j--; if (i<=j) { pom=a[i]; a[i]=a[j]; a[j]=pom; i++; j--; } } while (i<=j); if (l<j) qsort(l,j); if (i<r) qsort(i,r); } void main () { long n,i,p,k; double d,l; cin >> n >> l; for (i=1;i<=n;i++) cin >> a[i].x >> a[i].y; //------------------ p=1; for (i=2;i<=n;i++) if (a[p].y>a[i].y || (a[p].y==a[i].y && a[p].x>a[i].x)) p=i; pom=a[p]; a[p]=a[1]; a[1]=pom; a[1].ang=-2000000000; for (i=2;i<=n;i++) a[i].ang=atan2(a[i].y-a[1].y,a[i].x-a[1].x); qsort(1,n); a[n+1]=a[1]; p=1; for (i=2;i<=n;i++) if (a[i].y==a[1].y && a[i].x>a[p].x) p=i; if (p==1) p=2; convex[1]=a[1]; convex[2]=a[p]; k=2; for (i=p+1;i<=n+1;i++) if (a[i].y>a[1].y || i==n+1) { convex[++k]=a[i]; while (det(convex[k-2].x,convex[k-2].y,convex[k-1].x,convex[k- 1].y,convex[k].x,convex[k].y)<0 && k>2) convex[--k]=convex[k+1]; } //------------------ double pi; pi=3.14159265358979; d=0; for (i=1;i<k;i++) d+=sqrt((convex[i].x-convex[i+1].x)*(convex[i].x-convex[i+1].x)+ (convex[i].y-convex[i+1].y)*(convex[i].y-convex[i+1].y)); d+=(2*pi*l); //------------------ printf("%.0lf",d); } //thank's in advance! |
|
|