poj 1265 皮克定理＋多邊形面積＋邊上點的數量的求取

計算機幾何主要是結論：

１．皮克定理：　設sum_e是邊上整點的個數，可以通過gcd求取（不算起點）的整點數，設sum_i為内部的多邊形内部的整點，

多邊形的面積就是　area = sum_i +  sum_e/2 - 1

 2 . 多邊形面積：可以将多邊形拆分為多個三角形，三角形可以利用向量的叉積求取面積，即x1y2 -x2y1的一半

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#define MAX 107

using namespace std;

struct Point 
{
    int x,y;
}p[MAX];

int gcd ( int a , int b )
{
    return b == 0 ? a : gcd ( b , a%b );
}

int det ( Point p1 , Point p2 )
{
    return p1.x * p2.y - p1.y * p2.x;
}

int main ( )
{
    int t,n;
    scanf ( "%d" , &t );
    int c = 1;
    while ( t-- )
    {
        scanf ( "%d" , &n );
        int tx,ty;
        int sum_i = 0 , sum_e = 0 ;
        int area = 0;
        p[0].x = p[0].y =  0; 
        for ( int i = 1 ; i <= n ; i ++ )
        {
            scanf ( "%d%d" , &tx , &ty );
            sum_e += gcd ( abs(tx) , abs(ty) );
            p[i].x = p[i-1].x + tx;
            p[i].y = p[i-1].y + ty;
            area += det ( p[i-1] , p[i] );
        }
        if ( area < 0 ) area = -area;
        printf ( "Scenario #%d:\n", c++ );
        printf ( "%d %d %.1f\n\n",(area-sum_e+2)/2 , sum_e , 0.5*area ) ;
    }
}