POJ 2954(Pick公式)

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

Description

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

Input


多组数据。每一行输入x1y1x2y2x3,y3, 表示格点三角形 (x1y1), (x2y2),
(x3y3), −15000 ≤ x1y1x2y2x3y3 ≤ 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

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