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 [cpp] #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;} www.2cto.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; }
