首页 > 其他分享 >斯波的计几初探

斯波的计几初探

时间:2023-06-05 20:56:08浏览次数:38  
标签:node 计几 return int Convex 斯波 vec 初探 多边形

斯波的计几初探

一些基础

基础的基础

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

对于直线的记录,我们一般不设为\(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]);
    }
}

标签:node,计几,return,int,Convex,斯波,vec,初探,多边形
From: https://www.cnblogs.com/kid-magic/p/17458907.html

相关文章

  • 1 公式初探 Excel真正的力量
    用Excel来做记录是非常棒的使用公式来处理你的数据=数据1+数据2+...加减乘除均可即使你的数据有所变化,“引用”也可以使你的公式正常工作一定要为你的公式创建对应的立文本标签,这样日后当你查公式时,可以知道这些公式所表示的含义!可以对引用进行加减乘除使用单元格区......
  • backbone.js 初探[转]
    什么是backbonebackbone不是脊椎骨,而是帮助开发重量级的javascript应用的框架。主要提供了3个东西:1、models(模型)2、collections(集合)3、views(视图)backbone.js文件本身很小,压缩后只有5.3KB,作为一个框架级别的核心JS文件,这个数字很可怕。除此之外,这个JS还必须依赖于另一个JS文......
  • MES系统初探
    什么是MES系统MES系统是制造执行系统(ManufacturingExecutionSystem)的缩写,是一种用于监控、控制和优化制造过程的软件系统。它主要负责协调生产计划、生产调度、生产执行、质量管理、设备管理等方面的业务流程,实现生产过程的高效、精准和可控。MES系统通常与企业的ERP系统、SCAD......
  • windows域组策略初探
    【1】组策略(1.1)本地组策略rsop.msc(1.2)域组策略打开配置方式:《1》服务器管理器=》工具=》组策略管理《2》gpmc.msc如下图,全是组策略。 也可以右击某个策略,保存报告查看策略详情。 (1.3)非域控服务器获取当前域组策略的详细报告获取当前域组......
  • 使用VAE、CNN encoder+孤立森林检测ssl加密异常流的初探——真是一个忧伤的故事!!!
    sslpayload取1024字节,然后使用VAE检测异常的ssl流。代码如下:fromsklearn.model_selectionimporttrain_test_splitfromsklearn.preprocessingimportStandardScalerimportnumpyasnpimporttensorflowastfimporttflearnfrommatplotlibimportpyplotaspltimport......
  • C++ STL string初探:string类剖析
    一、string的基本概念1.1string是管理字符数组的类常见的初始化使用场景:无参构造和拷贝构造strings1;//无参构造strings2("helloworld");//有参构造对string类的总结:string是表示字符串的字符串类该类的接口与常规容器的接口基本相同,再添加了一些专门用来操作string的常规操......
  • 初探 ARM 半主机(Semihosting)及 QEMU 调试
    转载:[分享]初探ARM半主机(Semihosting)及QEMU调试-智能设备-看雪-安全社区|安全招聘|kanxue.com 我很想深入研究ARM 的 TrustZone,想要搭建一个可以模拟和调试Trusted Application 的平台环境。我了解到 Open-TEE(ATF)项目提供有一个 QEMU 模拟调试环境。虽然是针对......
  • 微软Playwright开源自动化框架初探-第一段代码和对应含义(首页截图)
    昨天我们已经在windows/mac上配置好了playwrigt框架,今天来写代码看看该框架怎么运行。 在写第一段代码之前,补充下上次没有讲完playwright框架的优点。跨浏览器、跨平台、跨语言、可测试的移动网络。适用于Android和Mobilesafiri的GoogleChrome原生移动仿真。相同的渲染引擎......
  • 微软Playwright开源自动化框架初探-安装和调试(java版)
    最近在研究部门的UI自动化框架(java+selenium+testNG+openCV等),发现在调试脚本时,需要先下载谷歌浏览器。无头/有头模式还需要代码区分。还有一个体验问题,程序启动太慢,从运行到浏览器启动,差不多需要30s左右,等得有点着急。  在知乎/CSDN中找到多篇文章推荐自动化测试利器-Playwrigh......
  • Kafka测试初探【Go】
    上周分享了Kafka性能测试初探的Java版本,有读者留言说太简单,内容比较水。这里澄清一下,是我学得比较水。文章定位就是一篇使用Java语言的KafkaClient客户端进行简单操作演示,然后模拟一下简单场景的性能测试。其中深入学习Kafka的可以随处搜到很权威实用的资料,有深入学习需求的可以自......