UVa1059/LA2395 Jacquard Circuits题目链接题意输入格式输出格式分析两个坑点AC 代码题目链接本题是2007年icpc世界总决赛(东京举办)的D题题意古怪的雕刻艺术家 Mondrian 发明了一种称为“提花织物电路板”的艺术品。该艺术品由一系列形状相同大小不同的多边形电路板构成层与层之间用细线连接如下图所示。方便起见我们借助于网格来制造这个艺术品。首先需要给定一个称为模板的格点多边形即各个顶点都是整点的简单多边形P代表电路板的形状。接下来寻找一个形状和P 相同的面积最小的格点多边形作为艺术品的第一层电路板然后找一个形状相同的面积第二小的格点多边形作为第二层依次类推共M1≤M≤1 000 000层。每个多边形内部的格点边界上的不算都会打一个洞你的任务是求出所有M 个多边形的洞的总数。P 是由N3≤N≤1 000个输入点顺次连接而成。输入格式输入包含一个或多个测试用例。每个测试用例的第一行包含两个正整数N3 ≤ N ≤ 1000和 M1 ≤ 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 } ggcd\{g_i\}ggcd{gi​}则最小的格点多边形 Q 是模板格点多边形 P 缩小g gg倍第 K 小的格点多边形是 Q 放大 K 倍。要求所有 M 个格点多边形内整点数总和将累加的公式推出来即可。两个坑点输入的点可能只是模板格点多边形边界上的点而非顶点。比如这条测试数据5 999999 2 2 2 3 2 4 3 4 4 4 0 0虽说最终答案不会超过 64 位有符号整数的最大值但中间涉及多次乘法再做减法再做除法中间计算结果可能溢出需要用 __int128_t 过渡一下。AC 代码#includeiostream#includealgorithmusingnamespacestd;#defineN1002longlongx[N],y[N],m;boolf[N];intn,kase0;boolcollinear(longlongx1,longlongy1,longlongx2,longlongy2,longlongx3,longlongy3){return(x2-x1)*(y3-y2)(x3-x2)*(y2-y1);}voidsolve(){for(inti0;in;i)cinx[i]y[i],f[i]true;for(inti0;in;i){intji?i-1:n-1,ki1n?0:i1;if(collinear(x[j],y[j],x[i],y[i],x[k],y[k]))f[i]false;}longlongg0,s0,t0;intk0;for(inti0;in;i)if(f[i])x[k]x[i],y[k]y[i];for(inti1;ik;i){longlongpxx[i-1],pyy[i-1],g1abs(__gcd(x[i]-px,y[i]-py));g__gcd(g,g1);tg1;s(x[i]-x[0])*(py-y[0])-(px-x[0])*(y[i]-y[0]);}longlongg1abs(__gcd(x[0]-x[k-1],y[0]-y[k-1]));g__gcd(g,g1);t(tg1)/g;sabs(s)/g/g;longlongans(m*__int128_t(m1)*(2*m1)/6*s-m*__int128_t(m1)/2*t)/2m;coutCase kase: ansendl;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);while(cinnm(m||n))solve();return0;}