求凸包
Andrew算法:
首先按照$x$为第一关键字,$y$为第二关键字从小到大排序,并删除重复的点
用栈维护凸包内的点
1、把$p_1, p_2$放入栈中
2、若$p_{i{(i > 3)}}$在直线$p_{i - 1}, p_{i - 2}$的右侧,则不断的弹出栈顶,直到该点在直线左侧
3、此时我们已经得到了下凸包,那么反过来从$p_n$再做一次即可得到下凸包
这里主要是更新一下模板
// luogu-judger-enable-o2
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int eps = 1e-10;
int dcmp(double x) {
if(fabs(x) < eps) return 0;
return x < 0 ? -1 : 1;
}
#define Point Vector
struct Vector {
double x, y;
Vector(double x = 0, double y = 0) : x(x), y(y) {};
bool operator < (const Vector &rhs) const {
return dcmp(x - rhs.x) == 0 ? y < rhs.y : x < rhs.x;
}
Vector operator - (const Vector &rhs) const {
return Vector(x - rhs.x, y - rhs.y);
}
};
double Cross(Vector A, Vector B) {
return A.x * B.y - A.y * B.x;
}
double dis(Point a, Point b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
int N;
Point p[10001], q[10001];
int top;
void Push(Point p) {
while(Cross(q[top] - q[top - 1], p - q[top - 1]) < 0) top--;
q[++top] = p;
}
void Andrew() {
q[0] = q[top = 1] = p[1];
for(int i = 2; i <= N; i++) Push(p[i]);
for(int i = N - 1; i; --i) Push(p[i]);
}
int main() {
scanf("%d", &N);
for(int i = 1; i <= N; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
sort(p + 1, p + N + 1);
Andrew();
double ans = 0;
for(int i = 1; i < top; i++)
ans += dis(q[i], q[i + 1]);
printf("%.2lf", ans);
return 0;
}