pku 2954 Triangle

Pick 定理的應(yīng)用

#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;
}