1 solutions
-
0
C++ :
#include<cstdio> #include<algorithm> #include<iostream> #include<cmath> using namespace std; int n,ss; struct point { double x,y; }p[10005],s[10005]; bool cmp(point p1,point p2) { if(p1.y==p2.y) return p1.x<p2.x; return p1.y<p2.y; } int mult(point p0,point p1,point p2) { return (p1.x-p0.x)*(p2.y-p0.y)>=(p2.x-p0.x)*(p1.y-p0.y); } int graham() { int i,j,k,top=1,mint; s[0]=p[0];s[1]=p[1]; for(i=2;i<n;i++) { while(top&&mult(p[i],s[top],s[top-1])) top--; s[++top]=p[i]; } mint=top;s[++top]=p[n-2]; for(i=n-3;i>=0;i--) { while(top!=mint&&mult(p[i],s[top],s[top-1])) top--; s[++top]=p[i]; } return top; } double f(point p1,point p2) { return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)); } void solve() { int i; double ans=0; ss=graham(); for(i=0;i<ss-1;i++) { ans+=f(s[i],s[i+1]); } ans+=f(s[0],s[ss-1]); printf("%.2lf\n",ans); } int main() { int i; scanf("%d",&n); for(i=0;i<n;i++) scanf("%lf %lf",&p[i].x,&p[i].y); if(n==0||n==1) printf("0.00\n"); else if(n==2) printf("%.2lf\n",f(p[0],p[1])); else { sort(p,p+n,cmp); solve(); } return 0; }
- 1
Information
- ID
- 19425
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- (None)
- Tags
- # Submissions
- 0
- Accepted
- 0
- Uploaded By