POJ 1113 二维凸包

题意：国王把自己城堡看成了一个点，让你找一个凸包把所有的城堡包住并且这个凸包距离城堡最近不能小于L，求这个凸包的最短长度。

题意就是求凸包最短长度再加上以L为半径的圆的周长就有解了。是一道使用Graham扫描法的模板题。一开始我用STL里的stack建栈，c++超时，g++985ms，而且感觉不是那么方便。之后我又用数组建栈写了，果断0ms，并且代码也没有那么长。

这个数组建栈的

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef double PointType;
struct point
{
    PointType x,y;
};
point data[1005],stack[1005],MinA;
int top;
PointType Direction(point pi,point pj,point pk) //判断向量PiPj在向量PiPk的顺逆时针方向 +顺-逆0共线
{
    return (pj.x-pi.x)*(pk.y-pi.y)-(pk.x-pi.x)*(pj.y-pi.y);
}
PointType Dis(point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(point a,point b)
{
    PointType k=Direction(MinA,a,b);
    if(k>0) return 1;
    if(k<0) return 0;
    return Dis(MinA,a)>Dis(MinA,b);
}
void Graham_Scan(point *a,int numa)
{
    for(int i=0; i<numa; i++)
        if(a[i].y<a[0].y||(a[i].y==a[0].y&&a[i].x<a[0].x))
            swap(a[i],a[0]);
    MinA=a[0],top=0;
    sort(a+1,a+numa,cmp);
    stack[top++]=a[0],stack[top++]=a[1],stack[top++]=a[2];
    for(int i=3; i<numa; i++)
    {
        while(Direction(stack[top-2],stack[top-1],a[i])<0)
            top--;
        stack[top++]=a[i];
    }
}
int main()
{
    int n;
    double r,pi=3.141592654;
    while(~scanf("%d%lf",&n,&r))
    {
        double sum=0;
        for(int i=0; i<n; i++)
            scanf("%lf%lf",&data[i].x,&data[i].y);
        Graham_Scan(data,n);
        for(int i=1; i<top; i++)
            sum+=Dis(stack[i],stack[i-1]);
        sum+=Dis(stack[0],stack[top-1]);
        sum+=pi*r*2;
        printf("%.0f\n",sum);
    }
    return 0;
}

这个是用STL的stack栈写的。。

#include <iostream>
#include<stack>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef double PointType;
struct point
{
    PointType x,y;
    int num;
};
point MinA;
point Next_To_Point(stack<point> temp)
{
    point first,second;
    first=temp.top();
    temp.pop();
    second=temp.top();
    temp.push(first);
    return second;
}
PointType Direction(point pi,point pj,point pk) //判断向量PiPj在向量PiPk的顺逆时针方向 +顺-逆0共线
{
    return (pj.x-pi.x)*(pk.y-pi.y)-(pk.x-pi.x)*(pj.y-pi.y);
}
PointType Dis(point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(point a,point b)
{
    PointType k=Direction(MinA,a,b);
    if(k>0) return 1;
    if(k<0) return 0;
    return Dis(MinA,a)>Dis(MinA,b);
}
stack<point> Graham_Scan(point *a,int numa)
{
    stack<point> s;
    for(int i=0; i<numa; i++)
        if(a[i].y<a[0].y||(a[i].y==a[0].y&&a[i].x<a[0].x))
            swap(a[i],a[0]);
    MinA=a[0];
    sort(a+1,a+numa,cmp);
    s.push(a[0]),s.push(a[1]),s.push(a[2]);
    for(int i=3; i<numa; i++)
    {
        while(Direction(Next_To_Point(s),s.top(),a[i])<0&&!s.empty())
            s.pop();
        s.push(a[i]);
    }
    return s;
}
point data[1005],st[1005];
int main()
{
    int n;double r,pi=3.141592654;stack<point> ans;
    while(~scanf("%d%lf",&n,&r))
    {
        double sum=0;int w=0;
        for(int i=0;i<n;i++)
        scanf("%lf%lf",&data[i].x,&data[i].y);
        ans=Graham_Scan(data,n);
        while(!ans.empty())
            st[w++]=ans.top(),ans.pop();
        for(int i=1;i<w;i++)
            sum+=Dis(st[i],st[i-1]);
        sum+=Dis(st[0],st[w-1]);
        sum+=pi*r*2;
        printf("%.0f\n",sum);
    }
    return 0;
}