UVa1059/LA2395 Jacquard Circuits

题目链接

本题是2007年icpc世界总决赛(东京举办)的D题

题意

古怪的雕刻艺术家 Mondrian 发明了一种称为“提花织物电路板”的艺术品。该艺术品由一系列形状相同，大小不同的多边形电路板构成，层与层之间用细线连接，如下图所示。

方便起见，我们借助于网格来制造这个艺术品。首先需要给定一个称为模板的格点多边形（即各个顶点都是整点的简单多边形）P，代表电路板的形状。接下来寻找一个形状和P 相同的，面积最小的格点多边形作为艺术品的第一层电路板，然后找一个形状相同的，面积第二小的格点多边形作为第二层，依次类推，共M（1≤M≤1 000 000）层。
每个多边形内部的格点（边界上的不算）都会打一个洞，你的任务是求出所有M 个多边形的洞的总数。P 是由N（3≤N≤1 000）个输入点顺次连接而成。

输入格式

输入包含一个或多个测试用例。每个测试用例的第一行包含两个正整数N（3 ≤ N ≤ 1000）和 M（1 ≤ M ≤ 1000000）。N 是 Mondrian 选取的格点数量，M 是完成后的雕塑的层级数。接下来的 N 行中，每行包含两个整数 x, y（|x|, |y| ≤ 1000000），表示模板格点多边形上某个点的坐标。这些点按顺时针或逆时针顺序列出。
最后一个测试用例后面跟着一行两个零。

输出格式

对于每个测试用例，输出一行，其中包含测试用例编号（从 1 开始），以及从给定图案的初始多边形开始构建的 M 层级雕塑中的孔洞数量。在任何情况下，该数值都不会超过 64 位有符号整数的最大值。

分析

利用 pick 定理即可求解本题。说一个如何求某条边( i − 1 , i ) (i-1,i)(i−1,i)内包含的整点数量的方法：∣ g c d ( x i − x i − 1 , y i − y i − 1 ) ∣ − 1 |gcd(x_i-x_{i-1},y_i-y_{i-1})|-1∣gcd(xi​−xi−1​,yi​−yi−1​)∣−1。如何找到面积最小的格点多边形呢？对每条边求出g i = ∣ g c d ( x i − x i − 1 , y i − y i − 1 ) ∣ g_i=|gcd(x_i-x_{i-1},y_i-y_{i-1})|gi​=∣gcd(xi​−xi−1​,yi​−yi−1​)∣，记g = g c d { g i } g=gcd\{g_i\}g=gcd{gi​}，则最小的格点多边形 Q 是模板格点多边形 P 缩小g gg倍，第 K 小的格点多边形是 Q 放大 K 倍。要求所有 M 个格点多边形内整点数总和，将累加的公式推出来即可。

两个坑点

1. 输入的点可能只是模板格点多边形边界上的点而非顶点。
   比如这条测试数据：

   5 999999 2 2 2 3 2 4 3 4 4 4 0 0

2. 虽说最终答案不会超过 64 位有符号整数的最大值，但中间涉及多次乘法再做减法再做除法，中间计算结果可能溢出，需要用 __int128_t 过渡一下。

AC 代码

#include<iostream>#include<algorithm>usingnamespacestd;#defineN1002longlongx[N],y[N],m;boolf[N];intn,kase=0;boolcollinear(longlongx1,longlongy1,longlongx2,longlongy2,longlongx3,longlongy3){return(x2-x1)*(y3-y2)==(x3-x2)*(y2-y1);}voidsolve(){for(inti=0;i<n;++i)cin>>x[i]>>y[i],f[i]=true;for(inti=0;i<n;++i){intj=i?i-1:n-1,k=i+1==n?0:i+1;if(collinear(x[j],y[j],x[i],y[i],x[k],y[k]))f[i]=false;}longlongg=0,s=0,t=0;intk=0;for(inti=0;i<n;++i)if(f[i])x[k]=x[i],y[k++]=y[i];for(inti=1;i<k;++i){longlongpx=x[i-1],py=y[i-1],g1=abs(__gcd(x[i]-px,y[i]-py));g=__gcd(g,g1);t+=g1;s+=(x[i]-x[0])*(py-y[0])-(px-x[0])*(y[i]-y[0]);}longlongg1=abs(__gcd(x[0]-x[k-1],y[0]-y[k-1]));g=__gcd(g,g1);t=(t+g1)/g;s=abs(s)/g/g;longlongans=(m*__int128_t(m+1)*(2*m+1)/6*s-m*__int128_t(m+1)/2*t)/2+m;cout<<"Case "<<++kase<<": "<<ans<<endl;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);while(cin>>n>>m&&(m||n))solve();return0;}