首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。