凸包



Andrew

1.将点按x为第一关键字,y为第二关键字排序

2.从左至右维护下半部分,从右至左维护上半部分

3.维护一个队列保证如果前一个向量在当前向量的左侧则直接推入,在右侧一直迭代至左侧为止


模板

给出二维平面内的所有点,求把这些点全部包含的最小周长。采用Andrew写法写即可。

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<double,double> PDD;
const int N = 1e4+10;
int n,stk[N];;
PDD q[N];
bool used[N];
PDD operator - (PDD a,PDD b)    {
    return {a.x-b.x,a.y-b.y};
}
double cross(PDD a,PDD b)
{
    return a.x*b.y-b.x*a.y;
}
double area(PDD a,PDD b,PDD c)
{
    return cross(b-a,c-a);
}
double get_dist(PDD a,PDD b)
{
    double dx=a.x-b.x;
    double dy=a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}
double andrew()
{
    sort(q,q+n);
    int top=0;
    for(int i=0;i<n;i++)
    {
        while(top>=2&&area(q[stk[top-1]],q[stk[top]],q[i])<=0)
        {
            if(area(q[stk[top-1]],q[stk[top]],q[i])<0)
                used[stk[top--]]=false;
            else    top--;
        }
        stk[++top]=i;
        used[i]=true;
    }
    used[0]=false;
    for(int i=n-1;i>=0;i--)
    {
        if(used[i]) continue;
        while(top>=2&&area(q[stk[top-1]],q[stk[top]],q[i])<=0)
            used[stk[top--]]=false;
        stk[++top]=i;
        used[i]=true;
    }
    double res=0;
    for(int i=2;i<=top;i++)
        res+=get_dist(q[stk[i-1]],q[stk[i]]);
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)    scanf("%lf%lf",&q[i].x,&q[i].y);
    double res=andrew();
    printf("%.2lf\n",res);
    return 0;
}

圆弧凸包

矩形四个角作了圆滑处理,使它们都是与矩形的两边相切的 1/4 圆,给出矩形长宽圆半径。这类解法可以根据圆的性质来推出每一段圆弧角度都等于外角,因外角和为360°,所以就是一个圆,其余就是对所有圆心做凸包即可。注意旋转向量的求法。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define x first
#define y second
using namespace std;
typedef pair<double,double> PDD;
const int N = 40010;
const double pi=acos(-1);
int n,cnt;
PDD q[N];
int stk[N],top;
bool used[N];
PDD rotate(PDD a,double b)
{
    return {a.x*cos(b)+a.y*sin(b),-a.x*sin(b)+a.y*cos(b)};
}
PDD operator -(PDD a,PDD b)
{
    return {a.x-b.x,a.y-b.y};
}
double cross(PDD a,PDD b)
{
    return a.x*b.y-a.y*b.x;
}
double area(PDD a,PDD b,PDD c)
{
    return cross(b-a,c-a);
}
double get_dist(PDD a,PDD b)
{
    double dx=a.x-b.x;
    double dy=a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}
double andrew()
{
    sort(q,q+cnt);
    for(int i=0;i<cnt;i++)
    {
        while(top>=2&&area(q[stk[top-1]],q[stk[top]],q[i])<=0)
        {
            if(area(q[stk[top-1]],q[stk[top]],q[i])<0)
                used[stk[top--]]=false;
            else top--;
        }
        stk[++top]=i;
        used[i]=true;
    }
    used[0]=0;
    for(int i=cnt-2;i>=0;i--)
    {
        if(used[i]) continue;
        while(top>=2&&area(q[stk[top-1]],q[stk[top]],q[i])<=0)
            top--;
        stk[++top]=i;
    }
    double res=0;
    for(int i=2;i<=top;i++)
        res+=get_dist(q[stk[i]],q[stk[i-1]]);
    return res;
}
int main()
{
    scanf("%d",&n);
    double a,b,r;
    scanf("%lf%lf%lf",&a,&b,&r);
    a=a/2-r,b=b/2-r;
    int dx[]={1,1,-1,-1},dy[]={1,-1,-1,1};
    while(n--)
    {
        double x,y,z;
        scanf("%lf%lf%lf",&x,&y,&z);
        for(int i=0;i<4;i++)
        {
            auto t=rotate({dx[i]*b,dy[i]*a},-z);
            q[cnt++]={x+t.x,y+t.y};
        }
    }
    double res=andrew();
    printf("%.2lf\n",res+2*pi*r);
    return 0;
}


文章作者: Dydong
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Dydong !
  目录