题目链接：http://poj.org/problem?id=1265
题目主要部分翻译：
You are hired to write a program that calculates the area occupied by the new facility from the movements of a robot along its walls. You can assume that this area is a polygon with corners on a rectangular grid. However, your boss insists that you use a formula he is so proud to have found somewhere. The formula relates the number I of grid points inside the polygon, the number E of grid points on the edges, and the total area A of the polygon. Unfortunately, you have lost the sheet on which he had written down that simple formula for you, so your first task is to find the formula yourself.
你被雇佣来写一个程序来计算被那个机器人占领的区域。你可以假设这个面积是一个由格点组成多边形。但是，你的老板要求你用一个公式，一个不知道他哪找来的公式。那个公式是和那个多边形内的格点数I、多边形边上的格点数E、多边形面积A有关。不幸的是，你丢失了那个写着那个简单公式的便签，所以你最先开始的任务是去找到那个公式。
给你该机器人的走的方向。dx，dy为x方向走的单位长度和y方向走的单位长度。求出I、E、A。
典型的pick公式的应用。。
S = a / 2 + b - 1。。一个很有趣的公式。。
那么就是求边界上的格点了。。gcd(abs(a.x - b.x), abs(a.y - b.y))。
知道这些个结论就比较easy了。。
Code:
#include <iostream>#include <algorithm>#include <cmath>#include <cstdio>#include <cstring>using namespace std;const int N = 1e2 + 5;struct POINT{ int x, y; POINT(){} POINT(int a, int b){ x = a; y = b; }} p[N];int n, k;int cross(POINT o, POINT a, POINT b){ return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);}int area(){ int ans = 0; for(int i = 1; i < n; i ++){ ans += cross(p[0], p[i], p[i + 1]); } return ans;}int gcd(int a, int b){ if(b == 0) return a; return gcd(b, a % b);}int OnEdge(){ int ans = 0; for(int i = 0; i < n; i ++){ ans += gcd(abs(p[i].x - p[i + 1].x), abs(p[i].y - p[i + 1].y)); } return ans ;}void solve(){ int s = area(); if(s < 0) s = - s; int I = OnEdge(); int E = s / 2 + 1 - I / 2; printf("Scenario #%d:n%d %d %.1fn", ++ k, E, I, s / 2.0);}int main(){// freopen("1.txt", "r", stdin); k = 0; int T; bool flag = false; scanf("%d", &T); while(T --){ int x, y; scanf("%d", &n); p[0] = POINT(0, 0); for(int i = 1; i <= n; i ++){ scanf("%d %d", &x, &y); p[i] = POINT(p[i - 1].x + x, p[i - 1].y + y); } if(flag) puts(""); solve(); flag = true; } return 0;}
pick公式就是这样的。。