计算几何

之前基本没认真学，但是准备 SCOI 还是必须学一下。

这玩意感觉多久没考过了，就 SCOI 一直出，真是服了，所以不得不学一下。

1.计算几何基础

Code

struct Point
{
    double x,y;
    const Point operator+(const Point &t)const{return (Point){x+t.x,y+t.y};}
    const Point operator-(const Point &t)const{return (Point){x-t.x,y-t.y};}
    const double operator*(const Point &t)const{return x*t.y-y*t.x;}
    const double operator^(const Point &t)const{return x*t.x+y*t.y;}
    const double len()const{return sqrt(x*x+y*y);}
    const Point rotate(double c){return {x*cos(c)-y*sin(c),x*sin(c)+y*cos(c)};}
};

2.二维凸包

1.Andrew 算法

我们将所有点按照 $x$ 坐标为关键字排序，之后用单调栈可以求出一半凸包。对于另一半再求一遍即可。

Code

int n;
Point a[N];
int top,sta[N];
bool used[N];
double ans;
inline bool cmp(const Point &x,const Point &y){return x.x!=y.x?x.x<y.x:x.y<y.y;}
inline void Andrew(int n,Point *a)
{
    memset(used,0,sizeof(used));
    sort(a+1,a+1+n,cmp);
    top=0;
    for(int i=1;i<=n;i++)
    {
        while(top>1&&(a[i]-a[sta[top-1]])*(a[sta[top]]-a[sta[top-1]])>0)
            used[sta[top--]]=0;
        used[sta[++top]=i]=1;
    }
    used[1]=0;
    for(int i=n;i;i--)
    {
        if(used[i])continue;
        while(top>1&&(a[i]-a[sta[top-1]])*(a[sta[top]]-a[sta[top-1]])>0)
            used[sta[top--]]=0;
        used[sta[++top]=i]=1;
    }
    for(int i=1;i<top;i++)ans+=(a[sta[i]]-a[sta[i+1]]).len();
}

2.1 例题

P3829 [SHOI2012] 信用卡凸包

注意到边缘的长度实际上就是一个圆的周长。于是直接求凸包然后加上就行了。

3.旋转卡壳

直观理解就是用两条平行线，“卡”住凸包上的一个点，然后再进行绕当前“卡”住的点 旋转直到再次 “卡”住凸包上的另一个点。

整体我们使用双指针扫一遍即可。