斯波的计几初探

一些基础

基础的基础

对于向量,直接坐标表示即可

对于直线的记录,我们一般不设为\(Ax+By+C=0\),而是记录方向向量和一个在直线上的点

对于多边形,我们一般采取一定顺序记录

\(\vec{a}\cdot\vec{b}=x_ax_b+y_ay_b\)

\(\vec{a}\times \vec{b}=x_ay_b-y_ax_b\)

叉乘本是三维空间特有的,但如果放在二维空间,我们可以以此来计算三角形面积以及\(\vec{a},\vec{b}\)的相对方向,如果为正则\(\vec{b}\)在\(\vec{a}\)的逆时针方向

判断一个点在直线的位置及距离

假设我们知道\(P(x_0,y_0)\in l\),\(l\)的方向向量\(\vec{n}\),要判断\(Q\)于\(l\)的位置关系

\(\overrightarrow{PQ}\times\vec{n} >0\),\(Q\)在下方,\(=0\)就在线上,\(<0\)就在直线的上方

对于距离,我们同样可以这样算,不过这里我们可以做一个勾股三角形\(d=\sqrt{ |\overrightarrow{PQ}|^2-|\dfrac{ \overrightarrow{PQ}\cdot\vec{n}}{|\vec{n}|}|^2}\)

判断两条线段是否相交

首先不能通过快速排斥实验,也就是两条线段框住的矩形必须有交

然后得通过排斥实验,也就是说一条线段的两个端点必须在另一条线段的两侧

多边形相关

判断一个点与多边形位置的关系

有什么光线算法还有回转数算法,思路都比较简单,但都有些麻烦,推荐用光线

如果是个凸多边形的话,我们可以在\(O(log(n))\)的时间内求解

考虑选一个多边形的任意一个点为起点,连上其他点成射线,我们只需二分看这个查询点在哪块区域即可,这里起点建议是最左下角,细节比较多

多边形的面积

很神奇,我愿称之为叉积的妙用

考虑对多边形三角剖分,然后随便选一个点\(O\),设\(v_i=\overrightarrow{OP_i}\)

按顺时针转,你会发现逆时针就是加

然后答案就是\(\dfrac{1}{2}\sum\limits_{i=0}v_i\times v_{(i+1)\bmod\ n}\)

多边形的重心

同样的三角剖分,然后对于每个三角形,直接加权平均算重心就行了

三角形的重心不难发现就是\((\dfrac{x_1+x_2+x_3}{3},\dfrac{y_1+y_2+y_3}{3})\),注意权就是有方向的面积

凸包

我们可以先按\(x\)排个序

然后毫无疑问,\(x\)最小的点是一定可以出现于凸包中的

先求下凸包

类似于斜率优化的方法

斜率肯定是递增的,具体反映到向量就是逆时针转,我们这样求到\(n\)也就是\(x\)最大的点

然后在剩下的点中求上凸壳,接在下凸壳后面即可

闽可夫斯基和

我们定义\(C=A+B=\{(x_a,y_a)+(x_b,y_b)\}\)

然后我们知道这个东西\(Convex(C)\)其实就\(Convex(A),Convex(B)\)转一圈得出的结果

你还会发现,这个\(Convex(C)\)的最左侧和\(Convex(A)\)的最左侧加\(Convex(B)\)的最左侧是相同的

于是我们可以选定最左侧的点作为起点,然后再对所有的边归并即可

eg1.[JSOI2018]战争

一个很简单的题,首先我们这里\(A_i=B_i+V\),即\(A_i-B_i=V\)

我们只需要\(A\),\(-B\)做闽可夫斯基和然后判断\(V\)是否在其中即可

eg2.某题

不难发现这里对模\(K=12\)分组,每一组都是下凸包

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e5+5;
const int K=12;
int n;
int k[MAXN];
int a[MAXN][5];
int sum[MAXN];
struct node{
    long long x,y;
    node operator+(const node a)const{
        return ((node){x+a.x,y+a.y});
    }
    node operator-(const node a)const{
        return ((node){x-a.x,y-a.y});
    }
};
vector<vector<node> >V[MAXN];
bool cmpx(node a,node b)
{
    if(a.x==b.x)
    {
        return a.y>b.y;
    }
    return a.x<b.x;
}
int st[MAXN];
int head=0;
long long cross(node a,node b)
{
    return a.x*b.y-a.y*b.x;
}
vector<node>M(vector<node>X,vector<node>Y)
{
    int i=0;
    int j=0;
    vector<node>Nl;
    Nl.clear();
    while(i<X.size()&&j<Y.size())
    {
        if(cmpx(X[i],Y[j]))
        {
            Nl.push_back(X[i]);
            i++;
        }
        else
        {
            Nl.push_back(Y[j]);
            j++;
        }
    }
    while(i<X.size())
    {
        Nl.push_back(X[i]);
        i++;
    }
    while(j<Y.size())
    {
        Nl.push_back(Y[j]);
        j++;
    }
    return Nl;
}
vector<node> Convex(vector<node>P)
{
    if(!(P.size()))
    {
        return P;
    }
    vector<node>D;
    D.clear();
    D.push_back(P[0]);
    for(int i=1;i<P.size();i++)
    {
    	if(D.back().x==P[i].x)
    	{
    		continue;
		}
		D.push_back(P[i]);
	}
	P=D;
    head=0;
    st[++head]=0;
    for(int i=1;i<P.size();i++)
    {
        while(head>=2&&cross(P[st[head]]-P[st[head-1]],P[i]-P[st[head]])>=0)
        {
            head--;
        }
        st[++head]=i;
    }   
    vector<node>R;
    R.clear();
    for(int i=1;i<=head;i++)
    {
        R.push_back(P[st[i]]);
    }
    return R;
}
node stl[MAXN],str[MAXN];
vector<node>Merge(vector<node>L,vector<node>R)
{
    if(L.size()==0)
    {
        return R;
    }
    int cntl=0;
    int cntr=0;
    for(int i=0;i<L.size()-1;i++)
    {
        stl[++cntl]=((L[i+1]-L[i]));
    }
    for(int i=0;i<R.size()-1;i++)
    {
        str[++cntr]=((R[i+1]-R[i]));
    }
    int i=1;
    int j=1;
    vector<node>D;
    D.clear();
    D.push_back(L[0]+R[0]);
    while(i<=cntl&&j<=cntr)
    {
        if(cross(stl[i],str[j])<=0)
        {
            D.push_back(D.back()+stl[i]);
            i++;
        }
        else
        {
            D.push_back(D.back()+str[j]);
            j++;
        }
    }
    while(i<=cntl)
    {
        D.push_back(D.back()+stl[i]);
        i++;
    }
    while(j<=cntr)
    {
        D.push_back(D.back()+str[j]);
        j++;
    }
    return D;
}
vector<vector<node> > solve(int l,int r)
{
    if(l==r)
    {
        return V[l];
    }
    int mid=(l+r)>>1;
    vector<vector<node> >L=solve(l,mid);
    vector<vector<node> >R=solve(mid+1,r);
    vector<vector<node> >D;
    D.resize(12);
    for(int i=0;i<K;i++)
    {
        D[i].clear();
    }
    for(int i=0;i<K;i++)
    {
        for(int j=0;j<K;j++)
        {
            if((L[i].size())&&(R[j].size()))
            {
                int To=(i+j)%K;
                vector<node>Tx=Merge(L[i],R[j]);
                D[To]=M(D[To],Tx);
            }
        }
    }
    for(int i=0;i<K;i++)
    {
        D[i]=Convex(D[i]);
    }
    return D;
}
long long Ans[MAXN];
int main()
{
    //freopen("date.in","r",stdin);
    //freopen("date.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&k[i]);
        k[i]--;
        sum[i]=sum[i-1]+k[i];
        for(int j=0;j<=k[i];j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        V[i].resize(12);
        for(int j=0;j<=k[i];j++)
        {
            V[i][j%K].push_back((node){j,a[i][j]});
        }
    }
    vector<vector<node> >Cx=solve(1,n);
    for(int i=0;i<K;i++)
    {
        for(int j=0;j<Cx[i].size();j++)
        {
            Ans[Cx[i][j].x]=max(Ans[Cx[i][j].x],Cx[i][j].y);
        }
    }
    for(int i=0;i<=sum[n];i++)
    {
        printf("%lld ",Ans[i]);
    }
}