首页 > 代码库 > pick定理:面积=内部整数点数+边上整数点数/2-1

pick定理:面积=内部整数点数+边上整数点数/2-1

 1 //pick定理:面积=内部整数点数+边上整数点数/2-1 2 // POJ 2954 3  4 #include <iostream> 5 #include <cstdio> 6 #include <cstdlib> 7 #include <algorithm> 8 #include <vector> 9 #include <math.h>10 using namespace std;11 #define LL long long12 typedef pair<int,int> pii;13 const double inf = 0x3f3f3f3f;14 const LL MOD =100000000LL;15 const int N =110;16 #define clc(a,b) memset(a,b,sizeof(a))17 const double eps = 1e-8;18 void fre() {freopen("in.txt","r",stdin);}19 void freout() {freopen("out.txt","w",stdout);}20 inline int read() {int x=0,f=1;char ch=getchar();while(ch>9||ch<0) {if(ch==-) f=-1; ch=getchar();}while(ch>=0&&ch<=9) {x=x*10+ch-0;ch=getchar();}return x*f;}21 22 int sgn(double x){23     if(fabs(x) < eps)return 0;24     if(x < 0)return -1;25     else return 1;26 }27 28 struct Point{29     int x,y;30     Point(){}31     Point(int _x,int _y){32         x = _x;y = _y;33     }34     Point operator -(const Point &b)const{35         return Point(x - b.x,y - b.y);36     }37     int operator ^(const Point &b)const{38         return x*b.y - y*b.x;39     }40     int operator *(const Point &b)const{41         return x*b.x + y*b.y;42     }43     friend bool operator<(const Point &a,const Point &b){44         if(fabs(a.y-b.y)<eps) return a.x<b.x;45         return a.y<b.y;46     }47 };48 49 int area(Point a,Point b,Point c){50     return fabs((a-c)^(b-c));51 }52 //求多边形边上整点的数目,顶点必须为整数点53 int fun(Point a,Point b){54     int x,y;55     x=abs(a.x-b.x);56     y=abs(a.y-b.y);57     return __gcd(x,y); 58 }59 int main(){60     // fre();61     int x1,y1,x2,y2,x3,y3;62     while(~scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3),x1||x2||x3||y1||y2||y3){63         int ans=area(Point(x1,y1),Point(x2,y2),Point(x3,y3));64         int cnt=0;65         Point a,b,c;66         a=Point(x1,y1);67         b=Point(x2,y2);68         c=Point(x3,y3);69         cnt+=fun(a,b);70         cnt+=fun(a,c);71         cnt+=fun(b,c);72         printf("%d\n",(ans-cnt)/2+1);73     }74     return 0;75 }

 

pick定理:面积=内部整数点数+边上整数点数/2-1