1 solutions

  • 0
    @ 2025-11-5 19:35:20

    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