HDU 1392 Surround the Trees[凸包]

1.题目
题目链接:点这儿!
2.解决方法
在一个二维平面上给出一个点集P,用一根橡皮筋将这些点捆住,形成的也就是一个由P组成的最小多边形,这个凸多边形被称作凸包;求凸包的周长,常见的有Graham扫描法、Andrew算法;后者是前者的改进,本题使用Andrew算法。

Andrew算法:将所有点按照x升序排序,若是x相等,则以y进行升序排序。从最左下方的点开始,求下凸壳;再从最右上方开始,求上凸壳。上下凸壳长度之和即为凸包周长。求凸壳的每一步,尽量将栈最上方两点构成的向量逆时针旋转。

3.代码

#include iostream
#include cstdio
#include cstring
#include algorithm
#include cmath

using namespace std;

const int MAXN=110;
const double eps=1e-8;

struct Node{
    double x,y;

    bool operator (const Node A){
        if(x!=A.x) return xA.x;
        return yA.y;
    }

    bool operator ==(const Node A){
        return A.x==xA.y==y;
    }

}s[MAXN];
int n;


Node stack[MAXN];

double Cross(Node O,Node A,Node B)//求向量OA与向量OB的叉积
{
    return (double)((A.x-O.x)*(B.y-O.y)-(double)(B.x-O.x)*(A.y-O.y));
}

double Distance(Node A,Node B)
{
    return (double)sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}

int sgn(double x)//判断x的正负性
{
    if(fabs(x)eps) return 0;
    else return x0?-1:1;
}

int main(void)
{
    while(cinnn){

        for(int i=0;in;i++) cins[i].xs[i].y;

        //Andrew算法
        sort(s,s+n);
        n=unique(s,s+n)-s;//删去重复点

        //求下凸壳
        int top=0;
        for(int i=0;in;i++){//叉积值为正,则将点B加入栈,否则说明当前栈顶A点不是凸包上的点,出栈
            while(top1sgn(Cross(stack[top-2],stack[top-1],s[i]))=0)
                top--;
            stack[top++]=s[i];
        }

        //再求上凸壳
        int j=top;
        for(int i=n-2;i=0;i--){
            while(topjsgn(Cross(stack[top-2],stack[top-1],s[i]))=0) top--;
            stack[top++]=s[i];
        }

        if(n1) top--;//避免重复计入最后一个点

        double ans=0.0;
        if(top==1)
            ans=0.0;
        else if(top==2)
            ans=Distance(stack[top-2],stack[top-1]);
        else{
            for(int i=0;itop;i++)//计算周长
                ans+=Distance(stack[i],stack[(i+1)%top]);
        }
        printf("%.2lf\n",ans);
    }

    return 0;
}
最新回复(0)
    /jishuzEVEvemtKUL_2FkKDEFKdkVzwZcvspV9BnqbfpOw_3D_3D4488614
    8