刚学土包,AndrewWA0pts求助
查看原帖
刚学土包,AndrewWA0pts求助
520056
luoyx楼主2023/8/15 18:15
#include <bits/stdc++.h>
using namespace std;
int n;
const int N=2e5+5;
struct vec{
	double x,y;
}p[N];
bool cmp(vec a,vec b){
	return a.x==b.x?a.y<b.y:a.x<a.x;
}
double cross(vec a,vec b){
	return a.x*b.y-a.y*b.x;
}
bool check(vec a,vec b,vec c){
	vec A={b.x-a.x,b.y-a.y};
	vec B={c.x-b.x,c.y-b.y};
	return cross(A,B)<=0;
}
vec st[N];
int tot;
double dis(vec a,vec b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>p[i].x>>p[i].y;
	}
	sort(p+1,p+n+1,cmp);
	if(n<3){
		cout<<-1;
		exit(0);
	}
	st[0]=p[1],st[1]=p[2],tot=1;
	for(int i=3;i<=n;i++){
		while(tot&&check(st[tot-1],st[tot],p[i])) tot--;
		st[++tot]=p[i];
	}
	st[++tot]=p[n-1];
	for(int i=n-2;i>=1;i--){
		while(tot&&check(st[tot-1],st[tot],p[i])) tot--;
		st[++tot]=p[i];
	}
	double ans=0;
	for(int i=0;i<tot;i++){
		ans+=dis(st[i],st[i+1]);
	}
	printf("%.2f",ans);
}
2023/8/15 18:15
加载中...