POJ2954 Triangle pick定理

版权声明：转载请注明出处 https://blog.csdn.net/jay__bryant/article/details/83721893

在平面直角坐标系中给定三角形的三个点的坐标(整数)，求该三角形内部的整点的数量

在平面直角坐标系中，以整点为顶点的简单多边形，其中内部整点数为a，边上（包括顶点）的整点数为b，则面积为S = a+b/2-1

一条端点为整点的线段上的整点的个数求法

#include <cstdio>
#include <cmath>

using namespace std;
int x,y,x2,y2,x3,y3;

int gcd(int a, int b)
{
    return b==0?a:gcd(b, a%b);
}

int abs(int x)
{
    return x>0?x:-x;
}

int main()
{
    while(~scanf("%d %d %d %d %d %d", &x,&y,&x2,&y2,&x3,&y3))
    {
        if(!x&&!y&&!x2&&!y2&&!x3&&!y3) break;
        int S = (x2-x)*(y3-y)-(y2-y)*(x3-x);
        if(S<0) S = -S;
        int on = gcd(abs(x2-x),abs(y2-y))+gcd(abs(x3-x),abs(y3-y))+gcd(abs(x2-x3),abs(y2-y3));
        int in = (S+2-on)/2;
        printf("%d
", in);
    }
    return 0;
}