Luogu P2742 [template] two dimensional convex hull

meaning of the title

Convex hull

Sol

Andrew algorithm:

First, rank $x $as the first key and $y $as the second key from small to large, and delete duplicate points

Using stack to maintain points in convex hull

1. Put $p UU 1, P UU 2 $in the stack

2. If $p {I {(I > 3)} $is to the right of the line $p {I - 1}, P {I - 2} $, the top of the stack will pop up until the point is to the left of the line

3. At this point, we have got the lower convex hull, and then we can get the lower convex hull by doing it again from $p_n $

Here is to update the template

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

Tags: C++

Posted on Fri, 31 Jan 2020 05:42:45 -0800 by ONiX