LuoGu P2735 电网 Electric Fences

时间:2020-12-25 16:25:49

题目传送门

这个东西,本来我是用求出两条一次函数解析式然后判断在x坐标下的y坐标值来做的

首先因为没考虑钝角三角形,WA了

然后又因为精度处理不好又WA了

一气之下,只能去网上查了查那个皮克定理

首先用皮克定理需要知道:在(0,0)到(n,m)这条线段上的整点个数有gcd(n,m)+1个,至于怎么证明,我没有深究(会用不就完了

这是对于一条过原点的线段,不过原点的线段呢?我是这样理解的:我把坐标系的原点平移到了该线段的的某个端点上,以这个点的坐标为原点,把上面的式子写出来,然后......就解决了

皮克定理:在网格点中三角形的面积: 2S = 2a + b - 2(我太懒了,复制一个吧

其中,s表示多边形面积,a表示图形内的格点数,b为图形边界上的格点数

然后利用推导公式(不就是逆用嘛):a=(2s-b+2)/2就行了。

但是嘞,又是该死的精度!

这样会造成一定的精度丢失,那怎么办?

尽量减少除法就行了!

把公式改为a=s-b/2+1,这样精度的问题就可以忽略了,然后就A掉了呢

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#define max(a,b) (a>b?a:b)
#define k1 (double(m)/double(n))
#define k2 (double(m)/double(n-p))
#define b (-p*k2) using namespace std; double n,m,p;
double tot; int main(){
scanf("%lf%lf%lf",&n,&m,&p);
tot=double(__gcd((int)n,(int)m)+__gcd((int)fabs(p-n),(int)m)+p);
printf("%.0lf\n",p*m/2-tot/2+1);
return 0;
}