「Luogu P2116」城墙

Description

给定 $n$ 个点，求出最短的包围所有点的轮廓且满足任意点到轮廓的距离不小于给定的 $L$ 。

$(3 \leq n \leq 10^3,1 \leq L \leq 10^3,-10^4 \leq x_i,y_i \leq 10^4)$

Source

[Luogu]P2116

Solution

所有点到轮廓的距离都 $\geq L$，显然取等于时是最优的。

因此轮廓一定由若干线段和圆弧构成。

而所有的线段都可以由点与点之间的连线平移得到，而且点围成的图形一定是一个凸多边形（凹多边形显然不优，比如图中的 $GH + HF > GF$）。也就是说线段的长度和就是凸包的长度。

那圆弧的长度呢？我们可以大胆猜想圆弧的总长刚好是一个圆周。

证明：

以图中底部的圆为例。

$\because IB$ 和 $CJ$ 分别是 $\odot A$ 和 $\odot D$，$\odot A$ 和 $\odot E$ 的外公切线，$AD \parallel IB,AE \parallel CJ$

$\therefore \angle DAB = \angle EAC = \angle ABI = \angle ACJ = 90^\circ$

$\therefore \angle DAE$ 与 $\angle BAC$ 互补

$\because$ $\angle DAE$ 与它的外角互补

$\therefore \angle BAC$ 等于 $\angle DAE$ 的外角

同理，每个圆弧所对的圆心角都是凸多边形的一个外角，而凸多边形的外角和为 $360^\circ$，因此圆弧的总长即是半径为 $L$ 的圆的周长。

凸包长度加上圆弧总长即是答案。时间复杂度为 $O(n \log n)$ 。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

const int MAXN = 1e3;
const double PI = acos(-1);
int n, l, top, tag;
double ans;
struct Vector {
    double x, y;
    
    inline friend bool operator<(Vector a, Vector b) {
        return a.x == b.x ? a.y < b.y : a.x < b.x;
    }
    inline friend Vector operator-(Vector a, Vector b) {
        return (Vector) { a.x - b.x, a.y - b.y };
    }
} a[MAXN + 5], sta[MAXN + 5];

inline double dist(Vector a, Vector b) {//两点的直线距离 
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

inline double cross(Vector a, Vector b) {//叉积 
    return a.x * b.y - a.y * b.x;
}

inline void getConvexHull(Vector *a, int n) {//求凸包长度 
    top = ans = 0;
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i) {
        for (; top > 1 && cross(sta[top] - sta[top - 1], a[i] - sta[top]) <= 0; --top);
        sta[++top] = a[i];
    }
    tag = top;
    for (int i = n - 1; i; --i) {
        for (; top > tag && cross(sta[top] - sta[top - 1], a[i] - sta[top]) <= 0; --top);
        sta[++top] = a[i];
    }
    for (int i = 1; i < top; ++i) ans += dist(sta[i], sta[i + 1]);
}

int main() {
    read(n), read(l);
    for (int i = 1; i <= n; ++i) scanf("%lf %lf", &a[i].x, &a[i].y);
    getConvexHull(a, n);
    ans += 2 * PI * l;//加上圆弧总长 
    printf("%.0lf\n", ans);
    return 0;
}