「Luogu P3829」「SHOI2012」信用卡凸包

Description

信用卡是一个矩形，唯四个角作了圆滑处理，使它们都是与矩形的两边相切的 $\frac{1}{4}$ 圆。现在平面上有 $n$ 张竖直方向长为 $a$，水平方向长为 $b$，圆半径为 $r$ 的信用卡，给定每张信用卡的坐标 $(x,y)$ 和旋转的弧度 $\theta$，试求其凸包的周长。注意凸包未必是多边形，因为它可能包含若干段圆弧。

$(1 \leq n \leq 10^4,0.1 \leq a,b \leq 10^6,0.0 \leq r < \min \{ \frac{a}{4},\frac{b}{4} \};|x|,|y| \leq 10^6, 0 \leq \theta < 2\pi)$

Source

[Luogu]P3829

Solution

包含所有信用卡的凸包一定由若干线段和圆弧构成。

我们可以把每张信用卡简化成一个矩形，矩形的四个顶点分别是其对应圆弧的圆心。

这个矩形上的每一个点到信用卡的轮廓距离刚好等于 $r$ 。于是问题就和 [Luogu]P2116 很相似了，唯一不同的地方在于点的处理（这里只分析该问题，其它过程详见链接）。

我们可以把这个矩形的四个顶点加入点集（比如说上图中的点 $A,B,C,D$）。具体求法为先假设信用卡中心为 $(0,0)$，得到的四个顶点分别为

$$\left( -\frac{b}{2} + r,\frac{a}{2} - r \right),\left( \frac{b}{2} - r,\frac{a}{2} - r \right),\left( -\frac{b}{2} + r,-\frac{a}{2} + r \right),\left( \frac{b}{2} - r,-\frac{a}{2} + r\right)$$

然后对这些点进行旋转，最后给每个顶点的坐标加上原来的中心坐标即可。

对点集中的点求凸包长度，即是所有线段的总长。而圆弧总长刚好是半径为 $r$ 的圆的周长，加起来即是答案。时间复杂度为 $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 = 4e4;
const double PI = acos(-1);
int n, m, top, tag;
double a, b, r, ans;
struct Vector {
    double x, y;
    
    Vector(double a = 0, double b = 0) {
        x = a, y = b;
    }
    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 };
    }
    inline friend Vector operator-(Vector a, Vector b) {
        return (Vector) { a.x - b.x, a.y - b.y };
    }
} v[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 rotate(Vector &a, double theta) {//逆时针旋转 theta (rad)
    double sinTheta = sin(theta), cosTheta = cos(theta);
    a = (Vector) { a.x * cosTheta - a.y * sinTheta, 
    a.x * sinTheta + a.y * cosTheta };
}

inline void getConvexHull(Vector *a, int n) {//求凸包长度 
    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);
    scanf("%lf %lf %lf", &a, &b, &r);
    for (int i = 1; i <= n; ++i) {
        double x, y, theta;
        scanf("%lf %lf %lf", &x, &y, &theta);
        Vector p = (Vector) { x, y }, 
        v1(-b / 2 + r, a / 2 - r), v2(b / 2 - r, a / 2 - r), //左上角，右上角 
        v3(-b / 2 + r, -a / 2 + r), v4(b / 2 - r, -a / 2 + r);//左下角，右下角 
        rotate(v1, theta), rotate(v2, theta);
        rotate(v3, theta), rotate(v4, theta);//旋转 
        v[++m] = v1 + p, v[++m] = v2 + p, v[++m] = v3 + p, v[++m] = v4 + p;
        //加上原来的中心坐标 
    }
    getConvexHull(v, m);
    ans += 2 * PI * r;//答案加上圆弧总长 
    printf("%.2lf\n", ans);
    return 0;
}