前两个点过不去
查看原帖
前两个点过不去
379420
Xuejiama1227楼主2023/5/27 11:41

rt

#include<bits/stdc++.h>
using namespace std;
template<typename T>
void read(T&x){
	x=0;char c=getchar();T f=1;
	for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
	for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c&15);
	x=x*f;
}
template<typename T,typename...Args>
void read(T&x,Args&...args){read(x);read(args...);}
int n;
struct point{
	double x,y;
}p[100005],s[100005];
bool cmp(point x,point y){return x.x<y.x||(x.x==y.x)&&(x.y<y.y);}
bool cmp2(point x,point y){return x.x==y.x&&x.y==y.y;}
double D(point x,point y){return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));}
double X(point x,point y){return x.x*y.y-x.y*y.x;}
double S(point x,point y,point z){return X({y.x-x.x,y.y-x.y},{z.x-x.x,z.y-x.y});}
int Andrew(){
	int tp,i;
	sort(p+1,p+n+1,cmp);
	n=unique(p+1,p+n+1,cmp2)-p-1;
	if(n<3)return -1;
	s[0]=p[1];s[1]=p[2];
	tp=1;
	for(i=3;i<=n;i++){
		while(tp&&S(s[tp-1],s[tp],p[i])<=0)tp--;
		s[++tp]=p[i];
	}
	s[++tp]=p[n-1];
	for(i=n-2;i>=1;i--){
		while(tp&&S(s[tp-1],s[tp],p[i])<=0)tp--;
		s[++tp]=p[i];
	}
	return tp;
}
signed main(){
	int i,tp;
	double ans=0;
	read(n);
	for(i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
	tp=Andrew();
	if(tp==-1)printf("-1");
	else{
		s[tp+1]=s[1];
		for(i=1;i<=tp;i++)ans+=D(s[i],s[i+1]);
		if(n==2)ans/=2;
		printf("%.2lf",ans);
	}
	return 0;
}
2023/5/27 11:41
加载中...