POJ 2954(Pick公式)


 
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)的格点数=易做图(abs(x1-x2),abs(y1-y2))+1
 
[cpp]  
#include<cstdio>  
#include<cstdlib>  
#include<cstring>  
#include<cmath>  
#include<iostream>  
#include<algorithm>  
#include<functional>  
using namespace std;  
#define MAXX (15000)  
int n;  
int 易做图(int a,int b){if (a<b) swap(a,b);if (b==0) return a;else return 易做图(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 易做图(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;}  www.zzzyk.com
    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;  
}

补充：软件开发 , C++ ,