poj 2954 Triangle 三角形内的整点数

poj 2954 Triangle

题意

给出一个三角形的三个点，问三角形内部有多少个整点。

解法

pick's law

一个多边形如果每个顶点都由整点构成,该多边形的面积为$S$,该多边形边上的整点为$L$,内部的整点为$N$,则有:

$ N + L/2 - 1 = S $
而对于两个点$A(x_1,y_1)$与$B(x_2,y_2)$，其边内部的整点数为：(不包含端点)
$ gcd ( abs(x_1 - x_2) , abs(y_1 - y_2) ) - 1 $

代码如下：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

#define INF 2139062143

#define MAX 0x7ffffffffffffff

#define del(a,b) memset(a,b,sizeof(a))

#define Rint register int

using namespace std;

typedef long long ll;

template<typename T>

inline void read(T&x)

{

    x=0;T k=1;char c=getchar();

    while(!isdigit(c)){if(c=='-')k=-1;c=getchar();}

    while(isdigit(c)){x=x*10+c-'0';c=getchar();}x*=k;

}

struct G{

	double x,y;

	G(double x=0.0,double y=0.0):x(x),y(y){}

};

G operator + (const G &a ,const G& b){return G(a.x+b.x,a.y+b.y);}

G operator - (const G &a ,const G& b){return G(a.x-b.x,a.y-b.y);}

double cross(G a,G b){

	return fabs(a.x*b.y-a.y*b.x);

}

struct node{

	int x,y;

};

node a[3];

int gcd(int a,int b){

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

}

int get_node(node a,node b){

	double x=fabs((double)a.x-b.x),y=fabs((double)a.y-b.y);

	if(x==0&&y==0) return 0;

	return gcd(x,y)-1;

}

int main()

{

	while(1){

		bool f=0;

		for(int i=0;i<3;i++){

			read(a[i].x),read(a[i].y);

			if(a[i].x || a[i].y) f=1;

		}

		if(!f) break;

		G b=G(a[1].x-a[0].x,a[1].y-a[0].y),c=G(a[2].x-a[0].x,a[2].y-a[0].y);

		int s=int(cross(b,c)/2);

		int L=get_node(a[0],a[1])+get_node(a[0],a[2])+get_node(a[2],a[1])+3;

		printf("%d\n",s+1-L/2);

	}

	return 0;

}