poj 1265 ||poj2954 pick公式 格子
poj 1265 ||poj2954 pick公式 网格
/ :求一个多边形中在网格内点的个数,在边上的点的个数,多边形的面积
//poj2954:求三角形内整点个数 ,两题大同小异,
/ :求一个多边形中在网格内点的个数,在边上的点的个数,多边形的面积
//poj2954:求三角形内整点个数 ,两题大同小异,
//利用pick公式:面积=内点+边上的点/2-1;
代码1:poj1265
#include<iostream> #include<cstdio> #include<math.h> #define abs(x)(x>=0? x:-x) int n; int gcd(int a,int b) { return b? gcd(b,a%b):a; } int area(int x1,int y1,int x2,int y2) { return (x1*y2-x2*y1); } int main() { int cas; scanf("%d",&cas); int k,i; for(k=1;k<=cas;k++) { scanf("%d",&n); int in=0; int on=0; int x1=0,y1=0,x2,y2; double res=0; for(i=0;i<n;i++) { int x,y; scanf("%d%d",&x,&y); on+=gcd(abs(x),abs(y)); x2=x1+x;y2=y1+y; res+=area(x1,y1,x2,y2); x1=x2;y1=y2; } printf("Scenario #%d:\n",k); res/=2.0; in=fabs(res)+1-on/2.0; printf("%d %d %0.1lf\n\n",in,on,res); } return 0; }
代码2:2954
#include<iostream> #include<cstdio> #include<math.h> int gcd(int a,int b) { return b? gcd(b,a%b): a; } struct point { int x,y; }; point p[3]; int grid_onedge(int n,point *p) { int i,ret=0; for(i=0;i<n;i++) { ret+=gcd(abs(p[i].x-p[(i+1)%n].x),abs(p[i].y-p[(i+1)%n].y)); } return ret; } int grid_inside(int n,point *p) { int i,ret=0; for(i=0;i<n;i++) { ret+=p[(i+1)%n].y*(p[i].x-p[(i+2)%n].x); } return (abs(ret)-grid_onedge(n,p))/2+1; } int main() { while(scanf("%d%d%d%d%d%d",&p[0].x,&p[0].y,&p[1].x,&p[1].y,&p[2].x,&p[2].y) ,p[0].x||p[0].y||p[1].x||p[1].y||p[2].x||p[2].y) { printf("%d\n",grid_inside(3,p)); } return 0; }