82ptsWa#1#2求调
查看原帖
82ptsWa#1#2求调
1114867
1nes楼主2024/5/21 17:02
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int N = 3e5 + 3;
int n;
struct point{
	double x , y;
	point(){}
	point(double x , double y):
		x(x) , y(y){}
}p[N] , st[N];
bool cmp(point a , point b){
	return a.x != b.x ? a.x < b.x : a.y < b.y;
}
double judge(point A , point B){
	return A.x * B.y - A.y * B.x;
}
double side(point a , point b , point p){
	point A = point(b.x - a.x , b.y - a.y);
	point B = point(p.x - a.x , p.y - a.y);
	return judge(A , B);
}
int andrew(){
	sort(p + 1 , p + 1 + n , cmp);
	st[0] = p[1] , st[1] = p[2];
	int top = 1;
	for(int i = 3 ; i <= n ; i++){
		while(top && side(st[top - 1] , st[top] , p[i]) <= 0)	top--;
		st[++top] = p[i];
	}
	st[++top] = p[n - 1];
	for(int i = n - 2 ; i >= 1 ; i--){
		while(top && side(st[top - 1] , st[top] , p[i]) <= 0)	top--;
		st[++top] = p[i];
	}
	return top;
}
double ed(point a , point b){
	double res1 = (a.x - b.x) * (a.x - b.x);
	double res2 = (a.y - b.y) * (a.y - b.y);
	return sqrt(res1 + res2);
} 
double ans;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);	
	cin >> n;
	for(int i = 1 ; i <= n ; i++)	cin >> p[i].x >> p[i].y;
	if(n < 3){
		printf("%.2lf\n" , ed(p[1] , p[n]));
		return 0;
	}
	int top = andrew();
	for(int i = 0 ; i < top ; i++){
		ans += ed(st[i] , st[i + 1]);
	}
	printf("%.2lf\n" , ans);
	return 0;
} 
2024/5/21 17:02
加载中...