p2735 电网

· · 题解

1定理：pick定理 pick定理是指一个计算点阵中顶点在格点上的多边形面积公式，该公式可以表示为2S=2a+b-2，其中a表示多边形内部的点数，b表示多边形边界上的点数，s表示多边形的面积。

2定理：（0,0）到（n,m）上点的个数=gcd(n,m)+1， 定理2就是扩展欧几里得的特殊情况

楼下的老哥有代码我就不贴了（其实知道这些代码已经很容易写了） ps.逆用pick定理时一定不能用（2s-b+2）/2，应该用s-b/2+1，不然会因为精度问题wa掉一个点