求助,第一个点wa了
查看原帖
求助,第一个点wa了
310914
x1024楼主2021/5/27 23:04
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int n,top=1;
double mx,my;
struct node
{
    double x,y;
}p[10005],sta[10005];
double cross(node a1,node a2,node b1,node b2) 
{
    return (a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y);
}
double dis(node p1,node p2) 
{
    return sqrt((p2.y-p1.y)*(p2.y-p1.y)+(p2.x-p1.x)*(p2.x-p1.x));
}
bool cmp(node p1,node p2) 
{
    double tmp=cross(p[1],p1,p[1],p2);
    if(tmp>0) 
		return 1;
    if(tmp==0&&dis(p[0],p1)<dis(p[0],p2)) 
		return 1;
    return 0;
}
void graham()
{
	for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&p[i].x,&p[i].y);
        double mid;
        if(i!=1&&p[i].y<p[1].y)
        {
        	mx=p[1].x;
			p[1].x=p[i].x;
			p[i].x=mx;
            my=p[1].y;
			p[1].y=p[i].y;
			p[i].y=my;
		}
    } 
    sort(p+2,p+1+n,cmp);
    sta[1]=p[1];
    for(int i=2;i<=n;i++)
    {
        while(top>1&&cross(sta[top-1],sta[top],sta[top],p[i])<=0)
			top--;
        top++;
        sta[top]=p[i];
    }
    sta[top+1]=p[1];
}
int main()
{
    scanf("%d",&n);
    graham();
    double ans=0.0; 
    for(int i=1;i<=top;i++) 
		ans+=dis(sta[i],sta[i+1]);
    printf("%.2lf\n",ans);
}
2021/5/27 23:04
加载中...