题解：P17369 [ECNA 2023] Convex Hull Extension

· · 题解

题意简述

给定一个按逆时针排列的严格凸整数多边形。统计可以加入的整数点，使新凸包保留全部原顶点、增加一个新顶点，且没有三个凸包顶点共线。若有无限多个答案，输出 infinitely many。

解题思路

加入新点后，原顶点的循环顺序不会改变。若全部原顶点都要保留，新点必然插入某一条原边的两个端点之间。因此，可以逐边统计该边能够插入的新点。

固定一条边 AB，记 A 的前一个顶点为 L，B 的后一个顶点为 R。新点 P 必须在有向边 AB 的右侧，并严格位于有向边 LA 和 BR 的左侧。这三个条件分别保证 A,P,B 处的三个新转角均为严格左转。

这三个条件也足够。新线段 AP 和 PB 除端点外都在 AB 右侧，而其余原边均在 AB 左侧，所以新多边形不会自交。所有转角都严格左转，便是严格凸多边形，全部原顶点都会保留。严格凸多边形也不可能存在三个共线顶点，否则中间那个点就不是极点。

不同原边对应的新点区域互不相交，因为新凸包中 P 的两个相邻原顶点唯一。于是各边的计数可以直接相加。

接下来对当前边建立保持整数格点的坐标变换。平移使 A=(0,0)，设向量 AB=(d_x,d_y)，令 g=\gcd(|d_x|,|d_y|)。用扩展欧几里得算法求出整数 u,v，使：

ud_x+vd_y=g

把原坐标 (x,y) 变换为：

\begin{cases} s=ux+vy \\ t=\frac{d_xy-d_yx}{g} \end{cases}

变换矩阵的行列式为 1，矩阵与逆矩阵均为整数矩阵。因此，变换前后的整数点一一对应，不会增添或丢失格点。变换后 A=(0,0)，B=(g,0)，需要统计的点位于下半平面，可记为 (s,-k)，其中 k 是正整数。

设变换后的 L 和 R 分别为 (s_L,t_L) 和 (s_R,t_R)。原多边形严格凸，故 t_L,t_R>0。将两条相邻边的严格左侧条件展开：

-\frac{s_L}{t_L}k<s<g+\frac{g-s_R}{t_R}k

记 a=-s_L、b=t_L、c=g-s_R、d=t_R，其中 b,d>0。在第 k 条整数水平线上，可选横坐标的区间就是：

\frac{ak}{b}<s<g+\frac{ck}{d}

区间宽度为 g-\frac{ad-bc}{bd}k。令 D=ad-bc，按其符号分类。

若 D<0，区间随 k 增大而变宽。充分大时，每条整数水平线上的区间都能包含整数，所以有无限多个答案。

若 D=0，得到宽度始终为整数 g 的平行带。这里不能直接判断为无限：开区间可能恰好夹在相邻两条整数竖线之间，一个格点也没有。

若 D>0，区间最终收缩为空。可能产生答案的行满足 Dk<gbd，所以仅需考虑：

1\le k\le K=\left\lfloor\frac{gbd-1}{D}\right\rfloor

分子减 1 利用了这些量均为整数，准确排除宽度为 0 的顶端。

对于一行 k，严格大于左端点的最小整数为 \lfloor ak/b\rfloor+1。严格小于右端点的最大整数为 g+\lfloor(ck-1)/d\rfloor。因此，该行的格点数为：

g+\left\lfloor\frac{ck-1}{d}\right\rfloor-\left\lfloor\frac{ak}{b}\right\rfloor

由于此时区间宽度为正，上式不会为负，无须再取最大值。它已经排除了三条边界上的全部整数点。

定义类欧几里得求和函数：

F(n,m,a,b)=\sum_{i=0}^{n-1}\left\lfloor\frac{ai+b}{m}\right\rfloor

将 k=1\sim K 换成从 0 开始的下标，当前边的有限贡献为：

Kg+F(K,d,c,c-1)-F(K,b,a,a)

系数 a,c 可能为负，求和函数必须实现数学上的向下取整，不能直接使用 C++ 对负数的截断除法。代码先取出系数和常数项的整商，使它们的余数落在 0\sim m-1，再进行通常的类欧几里得递推。

为说明递推，设此时 0\le a,b<m，令 Y=an+b。若 Y<m，所有项均为 0。否则令 n'=\lfloor Y/m\rfloor、b'=Y\bmod m。把求和理解为格点计数，再交换枚举的方向：

\begin{aligned} F(n,m,a,b) & =\sum_{j=1}^{n'}\left(n-\left\lceil\frac{mj-b}{a}\right\rceil\right) \\ & =\sum_{i=0}^{n'-1}\left\lfloor\frac{mi+b'}{a}\right\rfloor \\ & =F(n',a,m,b') \end{aligned}

第一行即使包含最上方额外的一层，其贡献也恰好为 0。第二行用 j=n'-i 代换。每次递推后新的分母是原来的 a<m，配合整商提取，过程与欧几里得算法相同。

代码中 exgcd 计算格点变换，floor_sum 计算 F。几何判断与求和全部使用整数，避免近平行边导致浮点误差。有限区域是底边为原边的三角形，结合坐标范围可知最终答案能放入 long long；求和中的大整商乘积及相减过程使用 __int128。

设坐标绝对值上界为 C，每条边进行一次扩展欧几里得和两次类欧几里得求和，总时间复杂度为 O(n\log C)，空间复杂度为 O(n)。

参考代码

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

using ll=long long;
using i128=__int128;
const int N=55;
ll x[N],y[N];
tuple<ll,ll,ll> exgcd(ll a,ll b)
{
    if(!b)return {a,1,0};
    auto [g,x,y]=exgcd(b,a%b);
    return {g,y,x-a/b*y};
}
i128 floor_sum(ll n,ll m,ll a,ll b)
{
    ll q=a/m;
    if(a%m<0)q--;
    a-=q*m;
    i128 res=(i128)q*n*(n-1)/2;
    q=b/m;
    if(b%m<0)q--;
    b-=q*m;
    res+=(i128)q*n;
    while(1)
    {
        res+=(i128)(a/m)*n*(n-1)/2+(i128)(b/m)*n;
        a%=m;
        b%=m;
        i128 y=(i128)a*n+b;
        if(y<m)break;
        n=y/m;
        b=y%m;
        swap(a,m);
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>x[i]>>y[i];
    ll ans=0;
    for(int i=0;i<n;i++)
    {
        ll dx=x[(i+1)%n]-x[i],dy=y[(i+1)%n]-y[i];
        auto [g,u,v]=exgcd(abs(dx),abs(dy));
        if(dx<0)u=-u;
        if(dy<0)v=-v;
        int j=(i+n-1)%n,k=(i+2)%n;
        ll a=-u*(x[j]-x[i])-v*(y[j]-y[i]),b=(dx*(y[j]-y[i])-dy*(x[j]-x[i]))/g,c=g-u*(x[k]-x[i])-v*(y[k]-y[i]),d=(dx*(y[k]-y[i])-dy*(x[k]-x[i]))/g;
        ll det=a*d-c*b;
        if(det<0||(det==0&&(g>1||a%b)))
        {
            cout<<"infinitely many"<<'\n';
            return 0;
        }
        if(!det)continue;
        ll m=(g*b*d-1)/det;
        ans+=(ll)((i128)m*g+floor_sum(m,d,c,c-1)-floor_sum(m,b,a,a));
    }
    cout<<ans<<'\n';
    return 0;
}