求救 第一个点 wa
查看原帖
求救 第一个点 wa
267778
sfksf楼主2021/11/30 10:33
#include <bits/stdc++.h>
using namespace std;
#define M 100005
#define ri register int

struct dian{
	double x,y;
}p[M];

bool cmp1(dian a,dian b)
{
	if(a.y==b.y) return a.x<b.x;
	return a.y<b.y;
}
bool cmp2(dian a,dian b)
{
	if(atan2(a.y-p[1].y,a.x-p[1].x)==atan2(b.y-p[1].y,b.x-p[1].x)) return a.x<b.x;
	return atan2(a.y-p[1].y,a.x-p[1].x)<atan2(b.y-p[1].y,b.x-p[1].x);
}
double ck(int a,int b,int c)
{
	return (p[b].x-p[a].x)*(p[c].y-p[a].y)-(p[c].x-p[a].x)*(p[b].y-p[a].y);
}
double dis(int a,int b)
{
	return sqrt((p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y));
}
int n,m;
int q[M];
int main(){
	
	scanf("%d",&n);
	for(ri i=1;i<=n;i++)
	scanf("%lf%lf",&p[i].x,&p[i].y);
	
	sort(p+1,p+1+n,cmp1);
	int top=1;
	q[top]=1;
	sort(p+2,p+1+n,cmp2);
	q[++top]=2;
	
	for(ri i=3;i<=n;i++)
	{
        while(top>=2&&ck(q[top-1],q[top],i)<=0)
        top--;
        q[++top]=i;
	}
	double ans=0;
	for(ri i=2;i<=top;i++)
	{
		ans+=dis(q[i],q[i-1]);
	}
	ans+=dis(q[top],1);
	printf("%0.2lf",ans);
	return 0;
	
}
2021/11/30 10:33
加载中...