POJ 1113 Wall (经典的基础凸包, Graham)

这篇博客是从旧博客 WordPress 迁移过来，内容可能存在转换异常。

分析：经典的凸包问题，且是最适合入门的一道凸包问题，我是用Graham Scan做的。题目给定一个简单多边形，求外围大于L的周长，由题目分析可知，只需要求出这个给定多边形的凸包，再加上一个以L为半径的圆周长即可，因为按照题意，距离多边形外围L的一个图形，由直线和圆弧组成，而所有的圆弧加起来就是一个圆形了(?为什么?自己画个图看看，所有圆弧的较就是多边形的内角，加起来就是2*PI)。所以~~~

AC代码，有点暴力，所以耗时200+ms

#include 
#include 
#include 
using namespace std;

const int MAXN = 1005;
const double PI = acos(-1.0);

typedef struct Point{
    int x;
    int y;
}Point;

Point p[MAXN]; // 保存输入结点
Point que[MAXN];  // 保存凸包结点，把que当一个栈来使用
int top;          // 记录栈顶位置

// 求a, b两点距离
double dis(Point a, Point b)
{
    return sqrt(double((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)));
}

// 求P0P1与P0P2的叉积
//叉乘,如果大于0,则说明直线P0P1在P0P2的顺时针方向，即P0P1在P0P2下面
int cross(Point p1,Point p2, Point p0)
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

// 用GrahamScan求凸包
void GrahamScan(int n)
{
    Point tmp;
    int k = 0;
    // ![0] 找出y值(y值相同时找x最小)最小的点作为起始点P0
    for(int i=1; i 0)
                || (cross(p[j], p[k], p[0])==0 && dis(p[0], p[j])=0)    //如果不能左转,则退栈
             top--;
        que[++top]=p[i];
    }
    // ![3]

    // ![4] 最后记得top要加1
    top++;
    // ![4]
}

int main()
{
    //freopen("input.txt", "r", stdin);
    int N, L;
    cin >> N >> L;
    for(int i=0; i> p[i].x >> p[i].y;
    GrahamScan(N);
    double ans = 0.0;
    for(int i=0; i<top; ++i)
        ans += dis(que[i], que[(i+1)%top]);
    ans += 2*PI*L;
    cout << (int)(ans+0.5) << endl;
    return 0;
}