RT

代码如下

convex_hull是核心代码

sgn是判断大小的

cross是叉积

我不理解为什么会被卡掉

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000005;
const double eps = 1e-8;
int sgn(double x) {
	if(abs(x)<eps) {
		return 0;
	}
	else if(x < 0)
	{
		return -1;
	}
	else
	{
		return 1;
	}
}
struct Point{
	double x, y;
	Point(){}
	Point(double x, double y):x(x), y(y){}
	Point operator + (Point B) {return Point(x+B.x,y+B.y);}
	Point operator - (Point B) {return Point(x-B.x,y-B.y);}
	bool operator == (Point B) {
		if(sgn(x-B.x) == 0 && sgn(y-B.y) == 0) 
			return true; 
		else return false;
	}
	bool operator < (Point B) {
		return sgn(x-B.x) < 0 || (sgn(x-B.x) == 0 && sgn(y-B.y) < 0);
	}
};
double Cross(Point A, Point B) {
	return A.x * B.y - A.y * B.x;
}
double Distance(Point A, Point B) {
	return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
int Convex_hull(Point *p, int n, Point *ch) {
	sort(p, p+n);
	n = unique(p, p+n) - p;
	int v = 0;
	for(int i=0; i<n; ++i) {
		while(v > 1 && sgn(Cross(ch[v-1]-ch[v-2], p[i]-ch[v-2])) <= 0) {
			v--;
		}
		ch[v++] = p[i];
	}
	int j = v;
	for(int i=n-2; i>=0; --i) {
		while(v > j && sgn(Cross(ch[v-1] - ch[v-2], p[i] - ch[v-2])) <= 0) {
			v--;
		}
		ch[v++] = p[i];
	}
	if(n > 1) v--;
	return v;
}
Point p[maxn], ch[maxn];
int main() {
	freopen("a.in","r",stdin);
	int n;
	cin >> n;
	for(int i=0; i<n; ++i) {
		cin >> p[i].x >> p[i].y;
	}
	int v = Convex_hull(p,n,ch);
	double ans = 0;
	if(v==1) {
		ans = 0;
	}
	else if(v == 2) {
		ans = Distance(ch[0],ch[1]);
	}
	else
	{
		for(int i=0; i<v; ++i) {
			ans += Distance(ch[i], ch[(i+1)%v]);
		}
	}
	printf("%.2lf\n", ans);
	return 0;
}