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、随意一个多边形的面积等于以多边形边上的某点为固定点。按顺序求其余点相邻两个点与该点组成的向量的叉积之和的一半。

本题都是从原点出发。能够都以原点为固定点。

思路:由于每一步的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;
}
时间: 04-12

poj 1265 Area(pick 定理)的相关文章

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 Pick定理

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

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

题目大意:以原点为起点然后每次增加一个x,y的值,求出来最后在多边形边上的点有多少个,内部的点有多少个,多边形的面积是多少. 分析: 1.以格子点为顶点的线段,覆盖的点的个数为GCD(dx,dy),其中,dxdy分别为线段横向占的点数和纵向占的点数.如果dx或dy为0,则覆盖的点数为dy或dx.2.Pick公式:平面上以格子点为顶点的简单多边形的面积=边上的点数/2+内部的点数+1.3.任意一个多边形的面积等于按顺序求相邻两个点与原点组成的向量的叉积之和. 代码如下: -------------

POJ 1265 Area Pick公式

题目大意:给出一个多边形的轮廓(以边的向量形式给出),求:1.有多少个整点在这个图形里面,2.有多少个点在图形内部,3.图形的面积是多少. 思路:首先明确Pick公式: 公式意义并不是让我们求出这个多边形的面积是多大,一是因为面积没必要用Pick公式求,二是没法求出多边形中间有多少整点.但是面积可以用叉积来求,多边形边上的整点可以用gcd来求,这样经过稍微的变形,就可以求解多边形中间有多少个整点了. CODE(c++AC,g++WA,求高人指点): #include <cstdio> #inc

POJ 1265 Area

Area Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 4713   Accepted: 2129 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 面积+多边形内点数

Area Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 5861   Accepted: 2612 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

POJ1265——Area(Pick定理+多边形面积)

Area DescriptionBeing well known for its highly innovative products, Merck would definitely be a good target for industrial espionage. To protect its brand-new research and development facility the company has installed the latest system of surveilla

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定理)

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