信用卡凸包问题

解题思路：

本题要求的是若干张明信片的凸包，每张明信片的四个角都是圆的。

如果明信片的四个角不是圆的，那么这题就会很好求，我们可以直接将所有矩形的顶点拿出来，然后求一个凸包就是答案。

但是实际上四个角是圆的，那么我们就需要考虑一些性质，首先可以发现求出的凸包一定是一堆直边，加上很多个圆弧，这些圆弧的长度不一定，但是所有边的长度都是固定的。

然后可以发现，一个圆弧两边延伸出去的两条直边，一定和这个圆弧对应的圆是相切的，因此这两条直线都是这个圆的切线。

圆和他的切线存在一个性质，就是圆心到切点之间连线，则这条线和切线是一定垂直。

我们将所有圆的圆心向他的两个切点连边。然后就可以将整个凸包划分成两个部分，一部分是若干条直边，一部分是若干条圆弧。

我们先看圆弧，对于一个圆弧，要想求这个圆弧的长度，我们需要知道这个圆弧的角度是多少，其实就是圆心到两个切点的两条边的夹角的度数，我们将他的两条切线延长相交，此时包括圆心角在内，会出现一个四边形，圆心到两个切点的两条边和切线的夹角都是 $90^。$，四边形的内角和是 $360^。$，因此圆心角和两条切线的夹角加起来就是 $180^。$，是互补的，因此圆心角的度数和两条切线的外角是相等的。

我们将每个圆弧的切线都延长相交，可以发现每个圆弧的圆心角度数就是对应的两条切线的外角，所有切线构成一个多边形，所有圆心角的度数和就是多边形的外角和，任意多边形的外角和都是 $180^。$，由于所有圆弧的半径都是相同的，因此所有圆弧合在一起，其实就是一整个圆。我们求一下一整个圆的周长，就是凸包中所有圆弧的长度之和。

然后对于任意两个相邻圆弧之间的直边，我们是可以将他平移到两个圆弧对应的圆心之间的，这样我们将所有直边都平移到他两端的圆弧对应的圆心上，此时所有直边合在一起刚好就是所有圆心的凸包。因此所有直边的长度之和就是所有圆心的凸包的周长。

综上所述，我们对所有圆弧的圆心求一个凸包，答案就是凸包的周长加上一整个圆的周长。

然后本题还有一个比较麻烦的点就是找出所有的矩形，题目给我们每个矩形的中心点和它逆时针旋转的角度，如果不旋转，四个点都比较好求，可以先求出中心点到四个点的向量，然后分别将四个向量逆时针旋转对应的角度，再加上中心的点的一个偏移量，就是明信片的四个角的位置，将一个向量旋转是一个比较常用的操作，可参考 计算几何的基础知识 。然后由于我们要求的不是矩形的四个顶点，而是四个圆心的位置，这里还需要注意不能搞错。

C++ 代码

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

const int N = 40010;
const double pi = acos(-1);

int n, m;
PDD q[N]; //存储所有点
int stk[N], top; //存储凸包中的所有点
bool st[N]; //记录每个点是否在凸包中

PDD rotate(PDD a, double b) //将向量 a 顺时针旋转 b 度
{
    return {a.x * cos(b) + a.y * sin(b), -a.x * sin(b) + a.y * cos(b)};
}

PDD operator-(PDD a, PDD b) //重载减号运算符
{
    return {a.x - b.x, a.y - b.y};
}

double cross(PDD a, PDD b) //求 a 和 b 的叉积
{
    return a.x * b.y - a.y * b.x;
}

double area(PDD a, PDD b, PDD c) //求 ab 和 ac 构成的平行四边形的有向面积
{
    return cross(b - a, c - a);
}

double get_dist(PDD a, PDD b) //求 a 到 b 的距离
{
    double x = a.x - b.x, y = a.y - b.y;
    return sqrt(x * x + y * y);
}

double andrew() //求凸包
{
    sort(q, q + m); //将所有点按照横纵坐标排序
    m = unique(q, q + m) - q; //将所有点判重

    //求上凸包
    for(int i = 0; i < m; i++)
    {
        while(top >= 2 && area(q[stk[top - 1]], q[stk[top]], q[i]) > 0) st[stk[top--]] = false;
        stk[++top] = i;
        st[i] = true;
    }

    //求下凸包
    st[0] = false;
    for(int i = m - 1; i >= 0; i--)
    {
        if(st[i]) continue;
        while(top >= 2 && area(q[stk[top - 1]], q[stk[top]], q[i]) > 0) top--;
        stk[++top] = i;
    }

    //求周长
    double res = 0;
    for(int i = 2; i <= top; i++) res += get_dist(q[stk[i - 1]], q[stk[i]]);
    return res;
}

int main()
{
    scanf("%d", &n);
    double a, b, r;
    scanf("%lf%lf%lf", &a, &b, &r);

    a = a / 2 - r, b = b / 2 - r;
    int dx[4] = {1, 1, -1, -1}, dy[4] = {1, -1, 1, -1}; //四个角的方向向量
    while(n--)
    {
        double x, y, z;
        scanf("%lf%lf%lf", &x, &y, &z);
        for(int i = 0; i < 4; i++)
        {
            PDD t = rotate({dx[i] * b, dy[i] * a}, -z); //旋转后的向量
            q[m++] = {x + t.x, y + t.y};
        }
    }

    double res = andrew(); //求凸包，并返回周长
    printf("%.2lf\n", res + 2 * pi * r);

    return 0;
}