首页 > > 程序设计 > C/C++ >

洛谷P2742 【模板】二维凸包

2018-07-27 06:10:27来源：博客园阅读 ()

题意

求凸包

Sol

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;
}