這個(gè)題用到2個(gè)計(jì)算幾何算法。求解凸包和簡(jiǎn)單多邊形面積。凸包算法詳細(xì)解釋見(jiàn)算法導(dǎo)論。求解多邊形面積的思想是將多邊形分解為三角
形，一般是假設(shè)按順序取多邊形上面連續(xù)的2點(diǎn)與原點(diǎn)組合成一個(gè)三角形，依次下去用叉積求有向面積之和，最后取絕對(duì)值即可。注意，這些
點(diǎn)必須是在多邊形上逆時(shí)針或者順時(shí)針給出的，而求出凸包剛好給了這樣的一系列點(diǎn)。
凸包代碼，其實(shí)先找出一個(gè)y坐標(biāo)最小的點(diǎn)，再對(duì)剩下的所有點(diǎn)按極角排序。然后對(duì)排序后的點(diǎn)進(jìn)行一個(gè)二維循環(huán)即可。二維循環(huán)的解釋是
當(dāng)加入新的點(diǎn)進(jìn)入凸包集合時(shí)候，如果與以前加入的點(diǎn)形成的偏轉(zhuǎn)方向不一致，那么前面那些點(diǎn)都需要彈出集合。
代碼如下：
#include <stdio.h>
#include <
string.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define MAX_N (10000 + 10)
struct Point
{
double x, y;
bool operator <(
const Point& p)
const {
return y < p.y || y == p.y && x < p.x;
}
};
Point pts[MAX_N];
int nN;
Point ans[MAX_N];
int nM;
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);
}
bool CrossCmp(
const Point& a,
const Point& b)
{
double cs = Cross(pts[0], a, b);
return cs > 0 || cs == 0 && a.x < b.x;
}
void Scan()
{
nM = 0;
sort(pts + 1, pts + nN, CrossCmp);
//對(duì)所有點(diǎn)按極角排序,逆時(shí)針偏轉(zhuǎn)
//第0-2個(gè)點(diǎn)，其實(shí)不會(huì)進(jìn)入第二重循環(huán)的
//從第3個(gè)點(diǎn)開(kāi)始，就依次檢查與凸包中前面點(diǎn)形成的邊的偏轉(zhuǎn)方向
//如果不是逆時(shí)針偏轉(zhuǎn)，則彈出該點(diǎn)
for (
int i = 0; i < nN; ++i)
{
while (nM >= 2 && Cross(ans[nM - 2], ans[nM - 1], pts[i]) <= 0)
{
nM--;
}
ans[nM++] = pts[i];
}
}
double GetArea()
{
double fAns = 0.0;
Point ori = {0.0, 0.0};
for (
int i = 0; i < nM; ++i)
{
fAns += Cross(ori, ans[i], ans[(i + 1) % nM]);
}
return fabs(fAns) * 0.5;
}
int main()
{
while (scanf("%d", &nN) == 1)
{
for (
int i = 0; i < nN; ++i)
{
scanf("%lf%lf", &pts[i].x, &pts[i].y);
if (pts[i] < pts[0])
{
swap(pts[i], pts[0]);
//pts[0]是y坐標(biāo)最小的點(diǎn)
}
}
Scan();
//掃描出凸包
double fArea = GetArea();
printf("%d\n", (
int)(fArea / 50));
}
return 0;
}