P2116 城墙 题解

· · 题解

Update on 2022.8.12：将代码中的 dis 函数换成了 std::hypot，l*6.2831853 换成了 std::numbers::pi*l*2（需要 <numbers> 头文件且需要 C++20）

前置知识：二维凸包

二维凸包模板传送门

OI Wiki

凸包的定义：在平面上能包含所有给定点的最小凸多边形叫做凸包。

求凸包的算法一般有两种，分别是 Andrew 算法和 Graham 算法，这里只介绍 Graham 算法。

Graham 算法的原理就是维护一个点集，通过扫描所有点向点集中不断添加更优的点和删除“凹”点最终形成凸包（因为如果一个凹多边形符合要求，那么必有一个凸多边形在周长上优于它，不然为什么不叫凹包）。

算法步骤

首先需要对点集排序。

Graham 算法快的一个很重要的原因就是因为预先进行了排序，所以可以减少扫描次数。

我们选择一个 y 值最小的点（这里记为 P_1），将剩余点按照极角的大小排序（这里记为 P_2 - P_5）

我们按照排序的顺序，依次连接每一个点，如果发现当前点 p[i] 与前两个点 p[i-1] 与 p[i-2] 形成了一个“凹壳”，那么点 p[i-1] 就肯定不在凸包的点集当中。

下面是图解：

首先连接 P_1P_2 和 P_2P_3 ，暂时没有发现问题。

连接 P_3P_4 ，依然没有发现问题。

连接 P_4P_5 ，问题来了，P_3P_4P_5 组成了一个“凹壳”，这样我们就应该把 P_4 踢出去，直接连接 P_3P_5 。

踢出 P_4 ，连接 P_3P_5 和 P_5P_1 ，凸包就求出来了。

回到本题。

P2116 城墙

题目要求最近距离不小于 L ,还要求周长最小值，那肯定恰好等于 L 是最优的。

按照题意画出图，可以发现要求的就是多边形外面围的这一圈，由若干圆弧和线段组成。

易得 P_1P_4IH 为矩形，所以 IH=P_1P_4 ，所以这一圈中的线段长度之和就是多边形周长。

怎么求多边形周长？可以用凸包求解，将给定点丢进凸包板子里就行了。

至于圆弧的总长度，猜想它就是一个圆的周长，也就是 2 \pi L 。

证明：易得在 \odot P_1 上的圆弧所对的圆心角与 \angle P_2P_4P_1 互补。

同理，每个圆弧所对的圆心角都与多边形的一个内角互补。

因为凸多边形的外角和为 360^{\circ} ，所以所有圆弧所对的圆心角之和为 360^{\circ} ，所以所有圆弧的长度之和就是一个圆的周长。

最终答案即为凸包周长 + 2 \pi L 。

双倍经验 UVA1303 Wall （注意细节，有多组数据，而且要输出两个换行，而且最后一组数据要少输出一个换行）

代码

#include<iostream>
#include<algorithm>
#include<numbers>
#include<cmath>
using namespace std;
int n,l,t=1;
double ans;
struct point
{
    double x,y;
}p[1005],s[1005];
double check(point a1,point a2,point b1,point b2)
{
    return (a1.x-a2.x)*(b1.y-b2.y)-(a1.y-a2.y)*(b1.x-b2.x);
}
bool cmp(point a,point b)
{
    double k=check(a,p[1],b,p[1]);
    if(k>0||(k==0&&hypot(a.x-p[1].x,a.y-p[1].y)<hypot(b.x-p[1].x,b.y-p[1].y)))  return 1;
    return 0;
}
int main()
{
    cin>>n>>l;
    for(int i=1;i<=n;i++)
    {
        cin>>p[i].x>>p[i].y;
        if(p[i].y<p[1].y)   swap(p[i],p[1]);
    }
    sort(p+2,p+n+1,cmp);
    s[1]=p[1];
    for(int i=2;i<=n;i++)
    {
        if(p[i-1].x==p[i].x&&p[i-1].y==p[i].y)  continue;
        while(t>1&&check(s[t],s[t-1],p[i],s[t])<0)  t--;
        s[++t]=p[i];
    }
    s[t+1]=p[1];
    for(int i=1;i<=t;i++)   ans+=hypot(s[i].x-s[i+1].x,s[i].y-s[i+1].y);
    cout<<round(ans+numbers::pi*l*2);
    return 0;
}