首页 > 代码库 > zoj1032解题报告

zoj1032解题报告

2024-07-30 03:47:00   220人阅读

一道几何题，开始不知道pick定理,于是就暴力..在一定范围内判断该点是否在多边形内,大致做法就是用该点作一条平行于x的射线，看与多边形的交点个数，其中注意的是若交点恰好为多边形的顶点要忽略.判断点是否在线段上,和求多边形面积可以用模板，结果超时..后来搜了下发现了pick定理,瞬间简单了很多. Pick定理:设以整数点为顶点的多边形的面积为S， 多边形内部的整数点数为N, 多边形边界上的整数点数为L， 则 N + L/2 - 1 = S. 果然像几何题，数论题不知道公式不行啊,只能多做这样题慢慢积累了. 代码如下: #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;struct node{ int x; int y;}point[105];int gcd(int m, int n){ if (m == 0) return n; if (n == 0) return m; while ((m%n)!=0) { int tmp = m % n; m = n; n = tmp; } return n;}int findL(node a,node b){ int dx = abs(int(a.x - b.x)); int dy = abs(int(a.y - b.y)); if(dx == 0 && dy == 0) return 0; if(dx == 0) return dy - 1; if(dy == 0) return dx - 1; return gcd(dx,dy) - 1;}double getarea(node a[],int n){ double area1 = 0,area2 = 0; for(int i = 0;i < n;i++){ area1 = area1 + a[(i+1)%n].y * a[i].x; area2 = area2 + a[(i+1)%n].y * a[(i+2)%n].x; } return fabs(area1 - area2)/2.0;}int main(){ int m,t; int ans = 1; scanf("%d",&t); while(t--){ scanf("%d",&m); point[0].x = point[0].y = 0; int x,y; for(int i = 1;i <= m;i++){ scanf("%d%d",&x,&y); point[i].x = point[i-1].x + x; point[i].y = point[i-1].y + y; } int N =0,L = 0; double A = 0; L = L + m + findL(point[0],point[m - 1]); for(int i = 0;i < m - 1;i++) L = L + findL(point[i],point[i+1]); A = getarea(point,m); N = (int)A - L/2 + 1; printf("Scenario #%d:\n",ans); printf("%d %d %.1lf\n\n",N,L,A); ans++; } return 0;}

zoj1032解题报告


联系
我们