POJ 1265 Area （计算几何）（Pick定理）

POJ 1265 Area （计算几何）（Pick定理）2015-02-25Area：http://poj.org/problem？id=1265

大意：每次给你一个点的横纵坐标变化值，求有多少点在多边形上，有多少点在多边形内，和多边形的面积。

思路：Pick定理。

一个计算点阵中顶点在格点上的多边形面积公式：S=a+b÷2-1，其中a表示多边形内部的点数，b表示多边形边界上的点数，s表示多边形的面积。

#include <map>#include <stack>#include <queue>#include <math.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <iostream>#include <limits.h>#include <algorithm>#define LL long long#define max（a,b） （（a）>（b）？（a）:（b））#define min（a,b） （（a）<（b）？（a）:（b））#define max3（a, b, c） （a>b？max（a, c）:max（b, c））#define min3（a, b, c） （a<b？min（a, c）:min（b, c））#define max4（a, b, c, d） max（max（a, b）, max（c, d））#define min4（a, b, c, d） min（min（a, b）, min（c, d））#define eps 1e-9#define INF 1 << 30using namespace std;int T, n;int cnt, Ans, a, b;struct Point{int x, y;} N[105];int Area（Point a, Point b）{return a.x*b.y-a.y*b.x;}int gcd（int a, int b）{if（b == 0）{return a;}else{return gcd（b, a%b）;}}void Solve（）{int T;scanf（"%d", &T）;for（int p = 1; p <= T; ++p）{scanf（"%d", &n）;Ans = cnt = N[0].x = N[0].y = 0;for（int i = 1; i <= n; ++i）{scanf（"%d%d", &a, &b）;N[i].x = N[i-1].x+a;N[i].y = N[i-1].y+b;Ans += Area（N[i], N[i-1]）;cnt += gcd（abs（a）, abs（b））;}Ans = abs（Ans）;printf（"Scenario #%d:
", p）;printf（"%d %d %.1lf

", （Ans-cnt+2）/2, cnt, Ans*0.5）;}}int main（void）{freopen（"data.in", "r", stdin）;//freopen（"data.out", "w", stdout）;Solve（）;return 0;}Area

From：cnblogs GLsilence