凸包

BB

计算几何菜鸡选手登场 QAQ

 

Introduction

凸包，通俗的讲，假设墙上有很多钉子，现在拿一根橡皮筋把钉子都围住，这个橡皮筋形成的图形即为凸包

 

【模板】二维凸包 / [USACO5.1]圈奶牛Fencing the Cows - Luogu P2742

Description
农夫约翰想要建造一个围栏用来围住他的奶牛，可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标，计算最短的能够围住这些点的围栏的长度。
Sample Input

4
4 8
4 12
5 9.3
7 8

Sample Output

12.00

Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<string, int> psi;
const int N = (int)1e4 + 15;
const double eps = 1e-6;

inline double sqr(double x) {
    return x * x;
}

inline double dcmp(double x) {
    return fabs(x) < eps ? 0 : (x > 0 ? 1 : -1);
}

struct Point {
    double x, y;

    bool operator < (const Point& b) const {
        return x != b.x ? x < b.x : y < b.y;
    }
    Point operator + (const Point& b) const {
        return Point{x + b.x, y + b.y};
    }
    Point operator - (const Point& b) const {
        return Point{x - b.x, y - b.y};
    }
};
typedef Point Vector;

bool used[N];
Point pt[N], resPt[N];
int stk[N], pstk;

double cross(const Point& a, const Point& b)  {
    return a.x * b.y - a.y * b.x;
}

inline double getDis(const Point& a, const Point& b) {
    return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
}

void Andrew(int n, Point* resPt, int& m) {
    memset(used, false, sizeof(used));
    sort(pt + 1, pt + 1 + n);
    pstk = 0;
    stk[++pstk] = 1;
    for(int i = 2; i <= n; i++) {
        while(pstk > 1 && dcmp(cross(pt[stk[pstk]] - pt[stk[pstk - 1]], pt[i] - pt[stk[pstk]])) <= 0) {
            used[stk[pstk--]] = false;
        }
        used[i] = true;
        stk[++pstk] = i;
    }
    int tmp = pstk;
    for(int i = n - 1; i >= 1; i--) {
        if(used[i]) {
            continue;
        }
        while(pstk > tmp && dcmp(cross(pt[stk[pstk]] - pt[stk[pstk - 1]], pt[i] - pt[stk[pstk]])) <= 0) {
            used[stk[pstk--]] = false;
        }
        used[i] = true;
        stk[++pstk] = i;
    }
    m = pstk;
    for(int i = 1; i <= m; i++) {
        resPt[i] = pt[stk[i]];
    }
}

int main() {
    int n;
    while(~scanf("%d", &n)) {
        for(int i = 1; i <= n; i++) {
            scanf("%lf%lf", &pt[i].x, &pt[i].y);
        }

        double ans = 0;
        if(n >= 2) {
            int m = 0;
            Andrew(n, resPt, m);

            for(int i = 2; i <= m; i++) {
                ans += getDis(resPt[i], resPt[i - 1]);
            }
        }
        printf("%.2f\n", ans);
    }

}

 

[SHOI2012]信用卡凸包 - Luogu P3829

Description
信用卡是一个矩形，唯四个角作了圆滑处理，使它们都是与矩形的两边相切的 1/4 圆，如下图所示。现在平面上有一些规格相同的信用卡，试求其凸包的周长。注意凸包未必是多边形，因为它可能包含若干段圆弧。
Sample Input

2
6.0 2.0 0.0
0.0 0.0 0.0
2.0 -2.0 1.5707963268
3
6.0 6.0 1.0
4.0 4.0 0.0
0.0 8.0 0.0
0.0 0.0 0.0
3
6.0 6.0 1.0
4.0 4.0 0.1745329252
0.0 8.0 0.3490658504
0.0 0.0 0.5235987756

Sample Output

21.66
41.60
41.63

Solution
看了一下题解原来是圆心的凸包 + 一个圆的周长 QAQ
（用逼近的方法水了40分，告辞 QAQ

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<string, int> psi;
const int N = (int)1e5 + 15;
const ll inf = (ll)9e18;
const int MOD = 998244353;
const double eps = 1e-6;
const double PI = acos(-1);

inline double sqr(double x) {
    return x * x;
}

inline double dcmp(double x) {
    return fabs(x) < eps ? 0 : (x > 0 ? 1 : -1);
}

struct Point {
    double x, y;

    bool operator < (const Point& b) const {
        return dcmp(x - b.x) != 0 ? dcmp(x - b.x) < 0 : dcmp(y - b.y) < 0;
    }
    Point operator + (const Point& b) const {
        return Point{x + b.x, y + b.y};
    }
    Point operator - (const Point& b) const {
        return Point{x - b.x, y - b.y};
    }
};
typedef Point Vector;

bool used[N];
Point pt[N], resPt[N];
Point initPt[N];
int stk[N], pstk;

double cross(const Point& a, const Point& b)  {
    return a.x * b.y - a.y * b.x;
}

inline double getDis(const Point& a, const Point& b) {
    return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
}

inline Vector rotate(const Vector& v, double a) {
    return Vector{v.x*cos(a) - v.y*sin(a), v.x*sin(a) + v.y*cos(a)};
}

void Andrew(int n, Point* resPt, int& m) {
    memset(used, false, sizeof(used));
    sort(pt + 1, pt + 1 + n);
    pstk = 0;
    stk[++pstk] = 1;
    for(int i = 2; i <= n; i++) {
        while(pstk > 1 && dcmp(cross(pt[stk[pstk]] - pt[stk[pstk - 1]], pt[i] - pt[stk[pstk]])) <= 0) {
            used[stk[pstk--]] = false;
        }
        used[i] = true;
        stk[++pstk] = i;
    }
    int tmp = pstk;
    for(int i = n - 1; i >= 1; i--) {
        if(used[i]) {
            continue;
        }
        while(pstk > tmp && dcmp(cross(pt[stk[pstk]] - pt[stk[pstk - 1]], pt[i] - pt[stk[pstk]])) <= 0) {
            used[stk[pstk--]] = false;
        }
        used[i] = true;
        stk[++pstk] = i;
    }
    m = pstk;
    for(int i = 1; i <= m; i++) {
        resPt[i] = pt[stk[i]];
    }
}

void getInitPt(double a, double b, double r, int& k) {
    const double dxTag[4] = {1, -1, -1, 1};
    const double dyTag[4] = {1, 1, -1, -1};
    for(int dy = 0; dy < 2; dy++) {
        for(int dx = 0; dx < 2; dx++) {
            int q = (dy << 1) | dx;
            initPt[++k] = Point{dxTag[q] * (b / 2 - r), dyTag[q] * (a / 2 - r)};
        }
    }
}

int main() {
    int n;
    while(~scanf("%d", &n)) {
        double a, b, r;
        scanf("%lf%lf%lf", &a, &b, &r);
        int k = 0;
        getInitPt(a, b, r, k);

        int m = 0;
        for(int i = 1; i <= n; i++) {
            double x, y, theta;
            scanf("%lf%lf%lf", &x, &y, &theta);
            for(int j = 1; j <= k; j++) {
                resPt[j] = rotate(initPt[j], theta) + Vector{x, y};
                pt[++m] = resPt[j];
            }
        }

        Andrew(m, resPt, k);
        double ans = 2 * PI * r;
        for(int i = 2; i <= k; i++) {
            ans += getDis(resPt[i - 1], resPt[i]);
        }
        printf("%.2f\n", ans);
    }
}