平面凸包算法：Jarvis步进法和Graham扫描法 。Jarvis步进法就好比有一条绳，把点集从外围一步一步包裹起来。Graham扫描法则先按极角排序，再一个个筛选。
以poj 1113 Wall为例，代码如下：
#include <stdio.h>
#include <math.h>
#define PI 3.1415926
#define N 1000
struct Point
{
int x, y;
}pnt[N];
void SwapPnt(int i, int j)
{
Point p = pnt[i];
pnt[i] = pnt[j];
pnt[j] = p;
}
// 如果向量oa顺时针移到向量ob，则为正（右手法则）
int CrossPdt(int o, int a, int b)
{
return (pnt[a].x – pnt[o].x) * (pnt[b].y – pnt[o].y) – (pnt[b].x – pnt[o].x) * (pnt[a].y – pnt[o].y);
}
int DisSqrt(int i, int j)
{
return (pnt[i].x – pnt[j].x) * (pnt[i].x – pnt[j].x) + (pnt[i].y – pnt[j].y) * (pnt[i].y – pnt[j].y);
}
int LowLeftPnt(int n)
{
int j = 0;
for (int i = 1; i < n; ++i)
{
if (pnt[j].y > pnt[i].y || pnt[j].y == pnt[i].y && pnt[j].x > pnt[i].x)
{
j = i;
}
}
return j;
}
/*
int Jarvis(int n)
{
int i, j;
// 寻找所有最下点中最左的点
j = LowLeftPnt(n);
SwapPnt(0, j);
// 以前一个点作为中心，将线顺时针旋转，截取线的最远点作为下一个中心
int center = 0;
while (center < n – 1)
{
j = center + 1;
for (i = center + 2; i < n; ++i)
{
if (CrossPdt(center, j, i) > 0 || CrossPdt(center, j, i) == 0
&& DisSqrt(center, j) < DisSqrt(center, i))
{
j = i;
}
}
// 优化前：只判断j点是否不在0~center围成的多边形内
//if (center >= 2 && CrossPdt(center, 0, j) <= 0)
//{
// break;
//}
// 优化前: end
SwapPnt(++center, j);
// 优化后：把0~center围成的多边形内的未选点去除
if (center >= 2)
{
i = center + 1;
while (i < n)
{
if (CrossPdt(center, 0, i) <= 0)
{
SwapPnt(i, –n);
}
else
{
++i;
}
}
}
// 优化后：end
}
return (center + 1);
}
*/
int Graham(int n)
{
int i, j;
j = LowLeftPnt(n);
SwapPnt(0, j);
// 按关于0点的极角从大到小从近到远排序，可改为快排
for (i = 1; i < n; ++i)
for (j = i + 1; j < n; ++j)
if (CrossPdt(0, i, j) > 0 || CrossPdt(0, i, j) == 0 && DisSqrt(i, 0) > DisSqrt(j, 0))
SwapPnt(i, j);
int top = 2; // 以pnt为栈，top指向最后进栈点
for (i = 3; i < n; ++i)
{
while (top > 0 && ( CrossPdt(top – 1, top, i) > 0 || CrossPdt(top – 1, top, i) == 0
&& DisSqrt(top, top-1) < DisSqrt(i, top-1) ))
{
–top;
}
pnt[++top] = pnt[i];
}
return (top + 1);
}
int main()
{
int n, gap;
scanf(“%d%d”, &n, &gap);
for (int i = 0; i < n; ++i)
{
scanf(“%d%d”, &(pnt[i].x), &(pnt[i].y));
}
//int cnt = Jarvis(n);
int cnt = Graham(n);
double sum = 2 * PI * gap;
for (int i = 0; i < cnt; ++i)
{
int j = (i + 1 + cnt) % cnt;
sum += sqrt(1.0 * DisSqrt(i, j));
}
printf(“%d\n”, int(sum + 0.5));
return 0;
}