此題用到了幾個(gè)知識(shí)，一個(gè)是求多邊形面積的公式。然后是，根據(jù)頂點(diǎn)都在整點(diǎn)上求多邊形邊界上的頂點(diǎn)數(shù)目的方法。最后一個(gè)是pick
定理。根據(jù)前面2個(gè)信息和pick定理算出在多邊形內(nèi)部的整點(diǎn)的個(gè)數(shù)。
求多邊形面積的方法還是叉積代表有向面積的原理，把原點(diǎn)看做另外的一個(gè)點(diǎn)去分割原來的多邊形為N個(gè)三角形，然后把它們的有向面
積加起來。
判斷邊界上點(diǎn)的個(gè)數(shù)是根據(jù)Gcd（dx,dy)代表當(dāng)前邊上整數(shù)點(diǎn)的個(gè)數(shù)的結(jié)論。這個(gè)結(jié)論的證明其實(shí)也比較簡單，假設(shè)dx = a，dy = b。
初始點(diǎn)是x0，y0，假設(shè)d = Gcd（a，b）。那么邊上的點(diǎn)可以被表示為（x0 + k * (a / d)，y0 + k * （b / d))。為了使點(diǎn)是整數(shù)點(diǎn)，
k必須是整數(shù)，而且0<= k <=d，所以最多有d個(gè)這個(gè)的點(diǎn)。
求多邊形內(nèi)部點(diǎn)的個(gè)數(shù)用的是pick定理。面積 = 內(nèi)部點(diǎn) + 邊界點(diǎn) / 2 - 1。
代碼如下：
#include <stdio.h>
#include <
string.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define MAX (100 + 10)
struct Point
{
double x, y;
};
Point pts[MAX];
int nN;
const int IN = 1;
const int EAGE = 2;
const int OUT = 3;
const double fPre = 1e-8;
double Det(
double fX1,
double fY1,
double fX2,
double fY2)
{
return fX1 * fY2 - fX2 * fY1;
}
double Cross(Point a, Point b, Point c)
{
return Det(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
}
double GetArea()
{
double fArea = 0.0;
Point ori = {0.0, 0.0};
for (
int i = 0; i < nN; ++i)
{
fArea += Cross(ori, pts[i], pts[(i + 1) % nN]);
}
return fabs(fArea) * 0.5;
}
int gcd(
int nX,
int nY)
{
if (nX < 0)
{
nX = -nX;
}
if (nY < 0)
{
nY = -nY;
}
if (nX < nY)
{
swap(nX, nY);
}
while (nY)
{
int nT = nY;
nY = nX % nY;
nX = nT;
}
return nX;
}
int main()
{
int nT;
int nI, nE;
double fArea;
scanf("%d", &nT);
int dx ,dy;
for (
int i = 1; i <= nT; ++i)
{
scanf("%d", &nN);
nI = nE = 0;
pts[0].x = pts[0].y = 0;
for (
int j = 1; j <= nN; ++j)
{
scanf("%d%d", &dx, &dy);
pts[j].x = pts[j - 1].x + dx;
pts[j].y = pts[j - 1].y + dy;
nE += gcd(dx, dy);
}
fArea = GetArea();
nI = (fArea + 1) - nE / 2;
printf("Scenario #%d:\n%d %d %.1f\n\n", i, nI, nE, fArea);
}
return 0;
}