POJ1265Area

http://poj.org/problem?id=1265

题意 ： 给你一个点阵，上边有很多点连成的多边形，让你求多边形内部的点和边界上的点以及多边形的面积，要注意他每次给出的点并不是点的横纵坐标，而是相对于上一个点的横纵坐标离开的距离dx，dy，所以你还要求一下每个点的坐标，然后再进行别的操作就可以了

思路 ：先用GCD函数求出边界上的点，用Pick公式求出边界多边形内部的格点数

Pick公式：给定顶点坐标均是整点的简单多边形，有：

面积=内部格点数目+边上格点数目/2-1；

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

using namespace std ;

struct node

{

    double x ;

    double y ;

    node() {}

    node(double a,double b):x(a),y(b){}

}ch[] ;

int m ;

double det(const node &a,const node &b)//计算两个向量的叉积

{

    return a.x*b.y-a.y*b.x;

}

double area()//求多边形的面积

{

    double sum = 0.0 ;

    ch[m]=ch[];

    for(int i =  ; i < m ; i++)

       sum += det(ch[i],ch[i+]) ;

    return sum/2.0 ;

}

int gcd(int a,int b)

{

    int temp ;

    if(a > b)

    {

        temp = a ;

        a = b ;

        b = temp ;

    }

    while(b != )

    {

        temp = a%b ;

        a = b ;

        b = temp ;

    }

    return a ;

}

int main()

{

    int n ;

    cin>>n ;

    for(int i =  ; i < n ; i++)

    {

        int count = ;

        cin>>m ;

        int xx =  , yy =  ,a,b;

        ch[].x = ;

        ch[].y = ;

        for(int j =  ; j < m ; j++)

        {

            cin>>a>>b ;

            count +=gcd(abs(a),abs(b)) ;//求边界格点数目

            ch[j+].x = a + xx ;

            ch[j+].y = b + yy ;

            xx = ch[j+].x ;

            yy = ch[j+].y ;

        }

        double sum = area() ;

        cout<<"Scenario #"<<i+<<":"<<endl;

        printf("%d %d %.1lf\n\n",int(sum)+-(count/),count,sum);

    }

}

注 ：GCD函数还有更简单的书写方式

int gcd(int a,int b)

{

    return b?gcd(b,a%b):a;

}