二维凸包 后面四个点过不去 求解 orz
  • 板块学术版
  • 楼主yzy12
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/4/23 21:29
  • 上次更新2023/11/5 00:12:10
查看原帖
二维凸包 后面四个点过不去 求解 orz
299315
yzy12楼主2021/4/23 21:29
#include"bits/stdc++.h"
using namespace std;
struct node{
	double x,y;
};
node a[100005],p[100005];
int n,tot;
double cc(node a,node b,node c){
	return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
double len(node a,node b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(node x,node y){
	int num=cc(a[1],x,y);
	if(num>0)return true;
	else if(num<0)return false;
	else return len(a[1],x)<len(a[1],y);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lf %lf",&a[i].x,&a[i].y);
	}
	for(int i=1;i<=n;i++){
		if(a[i].y<a[1].y){
			swap(a[1],a[i]);
		}
		else if(a[i].y==a[1].y&&a[i].x<a[1].x){
			swap(a[1],a[i]);
		}
	}
	sort(a+2,a+1+n,cmp);
	p[1]=a[1];
	p[2]=a[2];
	tot=2;
	for(int i=3;i<=n;i++){
		while(tot>=2&&cc(p[tot-1],p[tot],a[i])<=0)tot--;
		p[++tot]=a[i];
	}
	double ans=0;
	for(int i=1;i<tot;i++){
		ans+=len(p[i],p[i+1]);
 	}
	ans+=len(p[tot],p[1]);
	printf("%.2lf",ans);
	return 0;
}

2021/4/23 21:29
加载中...