萌新求助凸包,WA了7个点
查看原帖
萌新求助凸包,WA了7个点
257621
翼德天尊楼主2021/11/12 21:01
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100005
int n,st[N],stot;
double ans;
struct node{
	double x,y;
}p[N];
int read(){
	int w=0,fh=1;
	char c=getchar();
	while (c>'9'||c<'0'){
		if (c=='-') fh=-1;
		c=getchar();
	}
	while (c>='0'&&c<='9'){
		w=(w<<3)+(w<<1)+(c^48);
		c=getchar();
	}
	return w*fh;
}
bool cmp(node x,node y){
	return (x.x!=y.x)?(x.x<y.x):(x.y<y.y);
}
bool pd(int a,int b,int c){
	if (p[a].y<p[b].y){
		double k;
		if (p[a].x!=p[b].x) k=(p[a].y-p[b].y)/(p[a].x-p[b].x);
		else if (p[c].x>=p[b].x) return 1;
		else return 0;
		double zc=(p[c].y-p[a].y)/k+p[a].x;
		if (zc<p[c].x) return 1;
		else return 0;		
	}else{
		double k;
		if (p[a].x!=p[b].x) k=(p[a].y-p[b].y)/(p[a].x-p[b].x);
		else if (p[c].x<=p[b].x) return 1;
		else return 0;
		if (k==0){
			if (p[a].x<p[b].x)
				if (p[c].y<p[a].y) return 1;
				else return 0;
			else if (p[c].y>p[a].y) return 1;
			else return 0;
		}
		double zc=(p[c].y-p[a].y)/k+p[a].x;
		if (zc>p[c].x) return 1;
		else return 0;
	}

}
double dist(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 main(){
	n=read();
	for (int i=1;i<=n;i++) scanf("%lf %lf",&p[i].x,&p[i].y);
	sort(p+1,p+1+n,cmp); 
	st[++stot]=1,st[++stot]=2;
	ans+=dist(1,2);
	for (int i=3;i<=n;i++){
		if (stot>=2&&pd(st[stot-1],st[stot],i)) ans-=dist(st[stot],st[stot-1]),--stot;
		ans+=dist(st[stot],i);
		st[++stot]=i;
	}
	st[++stot]=n-1;
	ans+=dist(n,n-1);
	for (int i=n-2;i>=1;i--){
		if (stot>=2&&pd(st[stot-1],st[stot],i)) ans-=dist(st[stot],st[stot-1]),--stot;
		ans+=dist(st[stot],i);
		st[++stot]=i;
	}
	printf("%.2lf\n",ans);
	return 0;
	
}
2021/11/12 21:01
加载中...