题解：AT_agc051_e [AGC051E] Middle Point

· · 题解

Solution

有人往 NOI 模拟赛 T1 放这个。

祝搬题人和他的家人们身体健康，万事如意，天天开心！

定义有理数 r 是合法的，当前仅当存在整数 p 使得 2^p r \in \mathbb Z。

本质上给你若干个向量（凸包上的），然后求这些凸包的线性组合，要求系数和 =1 且所有系数都是合法的非负有理数。

凸包边界上的情况是容易处理的，考虑内部的点。内部的整点当然可以直接 pick 定理算，但是显然不是所有的整点都能构造到。

有结论：我们将一个向量移动到 (0,0) 之后，只需要要求所有系数是好的。证明略。

合法有理数关于 \pm 运算封闭，所以你可以做辗转相除。对于两个向量 (a,b) 和 (c,d)，我们一定会变为 (\gcd(a,c),\square) 和 (0,\triangle) 的形式。

所有 (0,\triangle) 依然可以辗转相除。也就是我们最后是 (a,b) 和 (0,c)。

合法有理数关于 \times 运算仍然封闭，所以我们可以让向量乘上 0.5。所以不妨设 c 是奇数。

如果 a 是奇数，那么彻底结束了（显然 a 取到了 \gcd \Delta_x 的不含 2 的最大公因数）。否则，如果 b 是奇数那么 (a,b) \leftarrow (a,b+c)。这样 b 是偶数，发现可以让 a 和 b 同时除以 2。感性理解这样做是对的，不过确实不太会证明，先这样吧。

这样坐标变换之后变成求凸包内整点个数。上面已经提到了可以用 pick 定理直接算。

大家觉得这个适合放在 T1 吗。

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=100+10;
int n,x[MAXN],y[MAXN],tot=0,ans;
struct Node {__int128 x,y;}st[MAXN*2],nst[MAXN*2];
Node A;
__int128 B;
__int128 dabs(__int128 v) {
    return (v>=0)?v:-v;
}
__int128 calc(Node A,Node B,Node C) {
    __int128 x=B.x-A.x,y=B.y-A.y;
    __int128 X=C.x-A.x,Y=C.y-A.y;
    return dabs(X*y-x*Y);
}
signed main() {
    freopen("aka.in","r",stdin);
    freopen("aka.out","w",stdout);
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    ffor(i,1,n) cin>>x[i]>>y[i];
    vector<pair<int,int>> vc;
    ffor(i,1,n) vc.push_back({x[i],y[i]});
    sort(vc.begin(),vc.end());
    ffor(i,1,n) x[i]=vc[i-1].first,y[i]=vc[i-1].second;
    int lst=1;
    ffor(i,1,n) {
        while(tot>lst&&(y[i]-st[tot].y)*(st[tot].x-st[tot-1].x)>(st[tot].y-st[tot-1].y)*(x[i]-st[tot].x)) --tot;
        st[++tot]={x[i],y[i]};
    }
    roff(i,n-1,1) {
        while(tot>lst&&(y[i]-st[tot].y)*(st[tot].x-st[tot-1].x)>(st[tot].y-st[tot-1].y)*(x[i]-st[tot].x)) --tot;
        st[++tot]={x[i],y[i]};
    }
    ffor(i,1,tot-1) {
        __int128 dt=__gcd(dabs(st[i].x-st[i+1].x),dabs(st[i].y-st[i+1].y));
        ans+=dt&-dt;
    }
    __int128 sx=st[1].x,sy=st[1].y;
    A={x[2]-sx,y[2]-sy};
    ffor(i,3,n) {
        Node AA={x[i]-sx,y[i]-sy};
        while(A.x&&AA.x) {
            __int128 del=A.x/AA.x;
            A.x-=AA.x*del,A.y-=AA.y*del;
            swap(A,AA);
        }
        if(AA.x) swap(A,AA); 
        B=__gcd(B,dabs(AA.y));
    }
    if(B) B/=(B&-B);
    while(1) {
        while(A.x%2==0&&A.y%2==0) A.x/=2,A.y/=2;
        if(A.x%2) break ;
        if(B) A.y+=B;
        else break ;
    }
    ffor(i,1,tot) {
        __int128 nx=(st[i].x-st[1].x),ny=(st[i].y-st[1].y);
        nst[i].x=nx/A.x;
        ny-=(nx/A.x)*A.y;
        if(ny) nst[i].y=ny/B;
    }
    __int128 S=0;
    ffor(i,2,tot-2) S+=calc(nst[1],nst[i],nst[i+1]);
    S=S+2;
    ffor(i,1,tot-1) S-=__gcd(dabs(nst[i+1].x-nst[i].x),dabs(nst[i+1].y-nst[i].y));
    cout<<(int)(S/2+ans);
    return 0;
}