Tag Archives: 格点多边形

POJ 2954(Pick公式)

Posted on by
Language:
Triangle
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 4203   Accepted: 1858

Description

求出一个已知3点坐标的格点三角形的里面(边上的不算)有多少点.

Input

多组数据。每一行输入x1, y1, x2, y2, x3,y3, 表示格点三角形 (x1, y1), (x2, y2),
(x3, y3), −15000 ≤ x1, y1, x2, y2, x3, y3 ≤ 15000. 数据以6个0结尾.

Output

每组数据输出一行，表示格点三角形里面的点数.

Sample Input

0 0 1 0 0 1
0 0 5 0 0 5
0 0 0 0 0 0

Sample Output

0
6

Source

Stanford Local 2004

Pick定理：S=I+E/2-1 (E表示格点多边形边上的点,I表示格点多边形内的点)

Pick推论：格点多边形S=0.5k (k是正整数)


边上格点数公式：线段(x1,y1)-(x2,y2)的格点数=gcd(abs(x1-x2),abs(y1-y2))+1


#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define MAXX (15000)
int n;
int gcd(int a,int b){if (a<b) swap(a,b);if (b==0) return a;else return gcd(b,a%b);}
struct P
{
	int x,y;
	P(){}
	P(int _x,int _y):x(_x),y(_y){}
	friend istream& operator>>(istream& cin,P &a){cin>>a.x>>a.y;return cin;	}
	friend bool operator||(bool b,P &a){return b||a.x||a.y;}
}a[3];
struct S
{
	P s,t;
	S(){}
	S(P _s,P _t):s(_s),t(_t){}
	friend bool operator||(bool b,S &a){return b||a.s||a.t;}
	friend bool operator||(S &a,S &b){return 0||a||b;}
	int dx(){return abs(t.x-s.x);}
	int dy(){return abs(t.y-s.y);}
	int E(){return gcd(dx(),dy())+1;}
};
struct T
{
	S c[3];
	S& operator[](int i){return c[i];}
	friend istream& operator>>(istream& cin,T &c){cin>>a[0]>>a[1]>>a[2];c[0]=S(a[0],a[1]);c[1]=S(a[1],a[2]);c[2]=S(a[2],a[0]);return cin;}
	friend bool operator&&(bool b,T &a){return b&&(a[0]||a[1]||a[2]);}
	int area2(){return c[0].s.x*c[1].s.y+c[1].s.x*c[2].s.y+c[2].s.x*c[0].s.y-c[1].s.x*c[0].s.y-c[2].s.x*c[1].s.y-c[0].s.x*c[2].s.y;}
	int E(){return c[0].E()+c[1].E()+c[2].E()-3;}
	double _S(){return (double)abs(area2())/2;}
	int I(){return _S()-E()/2+1;}
}c;
int main()
{
	while (cin>>c&&c)
	{
		cout<<c.I()<<endl;
	}
	return 0;
}