三角形内部坐标为整数值点的个数如何求
三角形为已知三角形,也就是三角形的三个顶点的坐标已固定,如何求在此三角形内部有多少个点的横纵坐标为整数?编写代码如下:
程序代码:
#include<bits/stdc++.h> using namespace std; int gcd(int x,int y) { return y==0?x:gcd(y,x%y);} int main() { int x1,y1,x2,y2,x3,y3; while(scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3)!=EOF) { if(!x1&&!y1&&!x2&&!y2&&!x3&&!y3) break; double edgnod=1.0*gcd(abs(x1-x2),abs(y1-y2))+gcd(abs(x1-x3),abs(y1-y3))+gcd(abs(x2-x3),abs(y2-y3)); double s=1.0*abs((x2-x1)*(y3-y1)-(y2-y1)*(x3-x1))/2; printf("%.0lf\n",s-edgnod/2+1); } return 0; }
该代码运行不能让人感到满意,运行一直不结束,请问该如何改呢?