这里是pick定理的应用。而且。这道题教会了我如何求两个整点间的整点的个数;
pku 2954 Triangle
Pick 定理的应用
#include "stdio.h"
#include "math.h"
typedef struct Point
{
int x,y;
}Point;
Point p[4];
int gcd(int n,int m)
{
if(m == 0) return n;
return gcd(m,n%m);
}
int Count(Point A,Point B)
{
int a,b,c,d;
if(A.x > B.x) { a = B.x; b = A.x; }
else { a = A.x; b = B.x; }
if(A.y > B.y) { c = B.y; d = A.y; }
else { c = A.y; d = B.y; }
b -= a;
d -= c;
return gcd(b,d) + 1;
}
int multi(Point A,Point B)
{
return A.x * B.y - A.y * B.x;
}
int area(Point *p, int n)
{
int ans = 0,i;
p[0] = p[n];
for(i = 0; i < n; i ++)
ans += multi(p[i],p[i+1]);
if(ans < 0) ans = -ans;
return ans;
}
int main()
{
int I,B,A;
while(1)
{
scanf("%d%d%d%d%d%d",&p[1].x,&p[1].y,&p[2].x,&p[2].y,&p[3].x,&p[3].y);
if(p[1].x==0&&p[1].y==0&&p[2].x==0&&p[2].y==0&&p[3].x==0&&p[3].y==0) break;
A = area(p,3);
B = Count(p[1],p[2])+Count(p[2],p[3])+Count(p[1],p[3]) - 3;
I = int((A-B)/2.0+1);
printf("%d\n",I);
}
return 0;
}
posted on 2010-08-16 09:51
崔佳星 阅读(302)
评论(0) 编辑 收藏 引用