求助凸包,Andrew,样例不过
查看原帖
求助凸包,Andrew,样例不过
365532
Mr_ll楼主2022/11/4 15:19
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
const int N=1e5+10;
int t,n,top,sta[N];
double ans;
struct qwe {
	double x,y;
	bool ty;
	double operator * (const qwe b)const {
		return x*b.y-y*b.x;
	}
	bool operator  <(const qwe b) const{
		if(x==b.x) return y<b.y;
		return x<b.x;
	}
	qwe operator -(const qwe b) const {
		qwe c;
		c.x=x-b.x;c.y=y-b.y;
		return c;
	} 
	double operator +(const qwe b) const {
		return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y));
	}
}p[N];
ll read() {
	ll x=0,f=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&(ch!='-')) ch=getchar(); 
	if(ch=='-') f=-1,ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
}
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);
	for(int i=1;i<=n;i++) {
		while(top>1&&(p[sta[top]]-p[sta[top-1]])*(p[i]-p[sta[top-1]])<=0) top--;
		sta[++top]=i;
	}
	int k=top;
	for(int i=n-1;i>=1;i--) {
		while(top>k&&(p[sta[top]]-p[sta[top-1]])*(p[i]-p[sta[top-1]])<=0) top--;
		sta[++top]=i;
	}
	for(int i=2;i<=top;i++) ans+=(p[i]+p[i-1]);
	ans+=(p[sta[1]]+p[sta[top]]);
	printf("%.2lf\n",ans);
	return 0;
} 
2022/11/4 15:19
加载中...