今天,心血来潮,花了一个下午时间学习了凸包,本来对着教程(文字)写代码,后来实在调不出来,只能对着别人的手模了。(太菜了)

我们先来看一道模板题:题目地址

题意:给出n个点,然后问你凸包(能包括所有点的一个图)的周长。。。

一道凸包经典题目。。。那么我们直接来讲凸包。。。

我学习了一种最为常见的算法:Graham扫描法

大概思想是先找到凸包上的一个点,然后从那个点开始按逆时针方向逐个找凸包上的点。。。我们已经知道如果已知凸包上的一个点,那么我们去找和他相邻的最外圈的点加入凸包。。。

所以我们如何找呢。。。这里就用到了二维叉积,已知两个向量 a 和 b,a×(叉)b就等于 (xa*yb)-(ya*xb)。。。如果其小于0,就表示a在b的逆时针方向。。。既然这样那我们就可以用叉积来求向量的位置关系。。。

步骤如下:

  1. 我们先在输入时找到y最小的那个点node[0],易得它一定在凸包里。。。
  2. 我们将所有的点(除了找出来的那个)按照幅角进行排序,方法就是利用叉积,我们比较两个点,从node[0]出发到这两个点变成两个向量。。。然后叉积判断位置。。。排完序以后,点都绕着node[0]按照逆时针排列。。。
  3. 我们O(n)枚举每一个点,看栈顶的元素和当前点与栈顶-1的元素构成的图是不是最优的,利用叉积,如果栈顶的元素在其逆时针,我们就将其pop出队列,直到符合条件,我们就直接把当前点加入队尾。。。

如下图:

20150530145453912

然后代码如下:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e4+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
namespace FastIO
{
    template inline void read(tp &x)
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x)
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
namespace Graham
{
    int n;
    struct Node{double x,y;int name;}node[N];
    vector v;
    void read_node()
    {
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&node[i].x,&node[i].y);
            if(node[i].y<node[0].y)
                swap(node[i].x,node[0].x),swap(node[i].y,node[0].y);
        }
        n--;
    }
    double Cross_product(Node a,Node b,Node c){return (b.x-a.x)*(c.y-b.y)-(c.x-b.x)*(b.y-a.y);}
    bool cmp(Node a,Node b)
    {
        double angle=(a.x-node[0].x)*(b.y-node[0].y)-(b.x-node[0].x)*(a.y-node[0].y);
        if(angle==0)return abs(a.x-node[0].x)<abs(b.x-node[0].x); 
        if(angle<0)return false;
        return true;
    }
    double solve()
    {
        double ans=0;v.push_back(node[0]);
        sort(node+1,node+n+1,cmp);
        for(int i=1;i1&&Cross_product(v[v.size()-2],v[v.size()-1],node[i])<=0) 
                v.pop_back();
            v.push_back(node[i]);
        }
        v.push_back(node[0]);
        for(int i=0;i<v.size()-1;i++)
            ans+=sqrt(pow(abs(v[i].x-v[i+1].x),2)+pow(abs(v[i].y-v[i+1].y),2));
        return ans;
    }
}
using namespace Graham;
main()
{
    read(n);
    read_node();
    printf("%.2lf",solve());
    return 0;
}

Leave A Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注