链接:poj 1265
题意:从原点出发,给出一些 dx,dy 移动增量,终于形成一个多边形,
求多边形内部的格点数目,边上的格点数目 ,以及面积。
补充知识:
1、以格子点为顶点的线段。覆盖的点的个数为 gcd(|dx|,|dy|),当中,|dx|,|dy | 分别为线段横向增量和纵向增量。 2、Pick 定理:设平面上以格子点为顶点的多边形的内部点个数为 a。边上点个数为 b,面积为 S, 则 S = a + b/2 -1.
3、随意一个多边形的面积等于以多边形边上的某点为固定点,按顺序求其余点相邻两个点与该点组成的向量的叉积之和的一半。本题都是从原点出发,能够都以原点为固定点。
思路:由于每一步的 dx,dy 已知,运用上述知识先求出边上点的个数,以及多边形面积,则内部点就可求出了
注:不要每算一次面积就取绝对值,要求叉积的累加和的绝对值
- #include < stdio.h > #include < stdlib.h > int chaji(int x1, int y1, int x2, int y2) {
- return x1 * y2 - x2 * y1;
- }
- int gcd(int a, int b) {
- return b == 0 ? a: gcd(b, a % b);
- }
- int main() {
- int T,
- m,
- i,
- j,
- dx,
- dy,
- n,
- b,
- x,
- y;
- float s;
- scanf("%d", &T);
- for (i = 1; i <= T; i++) {
- scanf("%d", &m);
- scanf("%d%d", &x, &y);
- b = gcd(abs(x), abs(y));
- s = 0;
- for (j = 2; j <= m; j++) {
- scanf("%d%d", &dx, &dy);
- b += gcd(abs(dx), abs(dy));
- s += chaji(x, y, x + dx, y + dy);
- x += dx;
- y += dy;
- }
- if (s < 0) s = -s;
- n = (s + 2 - b) / 2;
- printf("Scenario #%d:\n", i);
- printf("%d %d %.1f\n\n", n, b, s / 2);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2091673.html