Area - POJ 1265(pick定理求格点数+求多边形面积)

题目大意:以原点为起点然后每次增加一个x,y的值,求出来最后在多边形边上的点有多少个,内部的点有多少个,多边形的面积是多少。

分析:

1、以格子点为顶点的线段,覆盖的点的个数为GCD(dx,dy),其中,dxdy分别为线段横向占的点数和纵向占的点数。如果dx或dy为0,则覆盖的点数为dy或dx。
2、Pick公式:平面上以格子点为顶点的简单多边形的面积=边上的点数/2+内部的点数+1。
3、任意一个多边形的面积等于按顺序求相邻两个点与原点组成的向量的叉积之和。

代码如下:

-------------------------------------------------------------------------------------------------------------

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;

const int MAXN = 1e4+7;
const double EPS = 1e-10;

int GCD(int m, int n)
{
    if(!m || !n)
        return m+n;
    return GCD(n, m%n);
}

int main()
{
    int T, t=1;

    scanf("%d", &T);

    while(T--)
    {
        int N, x, y, nx=0, ny=0, cnt=0, area=0;

        scanf("%d", &N);

        for(int i=0; i<N; i++)
        {
            scanf("%d%d", &x, &y);

            cnt += GCD(abs(x), abs(y));
            x += nx, y += ny;
            area += (x*ny - y*nx);
            nx = x, ny = y;
        }
        if(area < 0)area = -area;
        printf("Scenario #%d:\n", t++);
        printf("%d %d %.1f\n\n", (area-cnt)/2+1, cnt, area/2.0);
    }

    return 0;
}
时间: 10-27

Area - POJ 1265(pick定理求格点数+求多边形面积)的相关文章

Area - POJ 1654(求多边形面积)

题目大意:从原点开始,1-4分别代表,向右下走,向右走,向右上走,向下走,5代表回到原点,6-9代表,向上走,向左下走,向左走,向左上走.求出最后的多边形面积. 分析:这个多边形面积很明显是不规则的,可以使用向量积直接求出来面积即可. 代码如下: ------------------------------------------------------------------------------------------------------------------------------

POJ 1265

主要利用PICK定理与边点数上的GCD的关系求解. 三角形一条边上的所有整数点(包括顶点)可以首先将这条边移到(0, 0)->(x, y).这时,(x/gcd(x, y), y/gcd(x, y))肯定在这条边上,并且是整数点,其余所有整数点的可以表示为k(x/gcd(x, y), y/gcd(x, y)).所以所有的整数点个数为gcd(x, y) + 1.即: b = gcd(x, y) + 1 #include <iostream> #include <cstdio> #

poj 1265 Area (Pick定理+求面积)

链接:http://poj.org/problem?id=1265 Area Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 4969   Accepted: 2231 Description Being well known for its highly innovative products, Merck would definitely be a good target for industrial espionag

POJ 1265 Area POJ 2954 Triangle Pick定理

Area Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 5227   Accepted: 2342 Description Being well known for its highly innovative products, Merck would definitely be a good target for industrial espionage. To protect its brand-new resear

poj 1265 Area(pick 定理)

链接:poj 1265 题意:从原点出发.给出一些dx,dy移动增量,终于形成一个多边形, 求多边形内部的格点数目,边上的格点数目 .以及面积. 补充知识: 1.以格子点为顶点的线段.覆盖的点的个数为gcd(|dx|,|dy|).当中,|dx|,|dy|分别为线段横向增量和纵向增量. 2.Pick定理:设平面上以格子点为顶点的多边形的内部点个数为a.边上点个数为b.面积为S,则 S = a + b/2 -1. 3.随意一个多边形的面积等于以多边形边上的某点为固定点.按顺序求其余点相邻两个点与该点

POJ题目1265 Area(PICK定理)

Area Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 5248   Accepted: 2352 Description Being well known for its highly innovative products, Merck would definitely be a good target for industrial espionage. To protect its brand-new resear

poj 1265 Area Pick定理

题目链接 pick定理: 一个计算点阵中顶点在格点上的多边形面积公式:S=a+b÷2-1,其中a表示多边形内部的点数,b表示多边形边界上的点数,s表示多边形的面积 知道这个这题就没有难度了. #include <iostream> #include <vector> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include &

poj 1265 Area(Pick定理)

Area Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 5666   Accepted: 2533 Description Being well known for its highly innovative products, Merck would definitely be a good target for industrial espionage. To protect its brand-new resear

POJ 1265 计算几何 多边形面积 内部格点数 边上格点数

链接: http://poj.org/problem?id=1265 题意: 给你一个多边形,求它的面积,内部格点数目,边上格点数目 题解: pick公式: 给定顶点坐标均是整数点的简单多边形,有 面积=内部格点数目+边上格点数目/2+1 边界上的格点数: 把每条边当做左开右闭的区间以避免重复,一条左开右闭的线段(x1,y1)->(x2,y2)上的格点数为: gcd(x2-x1,y2-y1). 代码: 1 #include <map> 2 #include <set> 3 #