这个东西,本来我是用求出两条一次函数解析式然后判断在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;
}