LINK

题意：给出一个简单几何，问与其边距离长为L的几何图形的周长。

思路：求一个几何图形的最小外接几何，就是求凸包，距离为L相当于再多增加上一个圆的周长（因为只有四个角）。看了黑书使用graham算法极角序求凸包会有点小问题，最好用水平序比较好。或者用Melkman算法

/** @Date    : 2017-07-13 14:17:05  * @FileName: POJ 1113 极角序求凸包 基础凸包.cpp  * @Platform: Windows  * @Author  : Lweleth (SoungEarlf@gmail.com)  * @Link    : https://github.com/  * @Version : $Id$  */#include <stdio.h>#include <iostream>#include <string.h>#include <algorithm>#include <utility>#include <vector>#include <map>#include <set>#include <string>#include <stack>#include <queue>#include <math.h>//#include <bits/stdc++.h>#define LL long long#define PII pair<int ,int>#define MP(x, y) make_pair((x),(y))#define fi first#define se second#define PB(x) push_back((x))#define MMG(x) memset((x), -1,sizeof(x))#define MMF(x) memset((x),0,sizeof(x))#define MMI(x) memset((x), INF, sizeof(x))using namespace std;const int INF = 0x3f3f3f3f;const int N = 1e5+20;const double eps = 1e-8;const double Pi = acos(-1.0);struct point{	int x, y;	point(){}	point(int _x, int _y){x = _x, y = _y;}	point operator -(const point &b) const	{		return point(x - b.x, y - b.y);	}	int operator *(const point &b) const 	{		return x * b.x + y * b.y;	}	int operator ^(const point &b) const	{		return x * b.y - y * b.x;	}};double xmult(point p1, point p2, point p0)  {      return (p1 - p0) ^ (p2 - p0);  }  double distc(point a, point b){	return sqrt((double)((b - a) * (b - a)));}int n, l;point p[N];stack<int>s;int cmp(point a, point b)//以p[0]基准 极角序排序{	int t = xmult(a, b, p[0]);	if(t > 0)		return 1;	if(t == 0)		return distc(a, p[0]) < distc(b, p[0]);	if(t < 0)		return 0;}void graham(){	while(!s.empty())		s.pop();	for(int i = 0; i < min(n, 2); i++)		s.push(i);	int t = 1;	for(int i = 2; i < n; i++)	{		while(s.size() > 1)		{			int p2 = s.top();			s.pop();			int p1 = s.top();			if(xmult(p[p1], p[p2], p[i]) > 0)			{				s.push(p2);				break;			} 		}		s.push(i);	}}int main(){	while(~scanf("%d%d", &n, &l))	{		int x, y;		int mix, miy;		mix = miy = INF;		int pos = -1;		for(int i = 0; i < n; i++)		{			scanf("%d%d", &x, &y);			p[i] = point(x, y);			if(miy > y || miy == y && mix > x)//注意选第一个点 是最左下方的			{				mix = x, miy = y;				pos = i;			}		}		swap(p[pos], p[0]);		sort(p + 1, p + n, cmp);		graham();		double ans = l * Pi * 2.0000;		int t = 0;		while(!s.empty())		{			ans += distc(p[t], p[s.top()]);			t = s.top();			s.pop();		}		printf("%d\n", (int)(ans + 0.500000));	}    return 0;}

POJ 1113 Wall 凸包 裸