Wa1求助
查看原帖
Wa1求助
605925
courtman楼主2023/1/11 18:52
#include<bits/stdc++.h>
#define lmw ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define int long long
using namespace std;
#define x first
#define y second
typedef pair<double,double> pdd;
const int N=1000010;
int n;
pdd q[N];
int s[N];
bool used[N];
double get_dist(pdd a,pdd b){
	double dx=a.x-b.x;
	double dy=a.y-b.y;
	return sqrt(dx*dx+dy*dy);
}
pdd operator-(pdd a,pdd b){
	return {a.x-b.x,a.y-b.y};
}
double cross(pdd a,pdd b){
	return a.x*b.y-a.y*b.x;
}
double area(pdd a ,pdd b,pdd c){
	pdd A=pdd(b.x-a.x,b.y-a.y);
	pdd B=pdd(c.x-a.x,c.y-a.y); 
	return cross(A,B);
}
double andrew(){
	sort(q,q+n);
	int top=0;
	for(int i=0;i<n;i++){
		while(top>=2&&area(q[s[top-1]],q[s[top]],q[i])>=0){
			used[s[top--]]=0;
		}
		s[++top]=i;
		used[i]=1;
	}
	used[0]=0;
	for(int i=n-1;i>=0;i--){
		if(used[i]) continue;
		while(top>=2&&area(q[s[top-1]],q[s[top]],q[i])>=0) top--;
		s[++top]=i;
	}
	double res=0.0;
	for(int i=2;i<=top;i++){
		res+=get_dist(q[s[i-1]],q[s[i]]);
	}
	return res;
}
signed main(){
    lmw;    
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>q[i].x>>q[i].y;
	}
	double res=andrew();
	cout<<fixed<<setprecision(2)<<res<<"\n";
}
2023/1/11 18:52
加载中...