首页 > 其他分享 >Max_QAQ 计算几何

Max_QAQ 计算几何

时间:2023-08-09 10:27:22浏览次数:46  
标签:直线 QAQ cdot Max 线段 凸包 多边形 几何 theta

目录

二维计算几何基础

点、向量、直线

点:\((x,y)\) .

向量:\((x,y)\) .

向量的运算(\(A=(a_1,a_2),\ B=(b_1,b_2)\)):

  • 加减:\(A\pm B=(a_1\pm b_1,a_2\pm b_2)\)

  • 数乘:\(k\cdot A=(k\cdot a_1,k\cdot a_2)\)

  • 模长:\(|A|=\sqrt{a_1^2+a_2^2}\) .

  • 幅角:\(\theta=\arctan\frac{a_2}{a_1}\)(可以用 atan2 求).

    因为是 \(\tan\theta=\frac{a_2}{a_1}\),所以一般情况极角排序(按幅角排序)可以用斜率排 .

  • 点积:\(A\cdot B=a_1b_1+a_2b_2=|A|\cdot |B|\cdot\cos\theta\) .

    判断夹角:\(A\cdot B>0\) 锐角,\(A\cdot B=0\) 直角,\(A\cdot B<0\) 钝角 .

  • 叉积:\(A\times B=a_1b_2-b_1a_2=|A|\cdot |B|\cdot\sin\theta\)(有向面积).

    可以看成行列式:\(A\times B=\begin{vmatrix}a_1&a_2\\b_1&b_2\end{vmatrix}\) .

    判断方向:\(A\cdot B>0\) 逆时针,\(A\cdot B=0\) 共线,\(A\cdot B<0\) 顺时针 .

  • 旋转:\((a_1,a_2)\) 转 \(\theta\):\((a_1\cos\theta-a_2\sin\theta,a_1\sin\theta+a_2\cos\theta)\) .

直线:记两个点 \(A,B\),那么如果向量 \(\bm v=B-A\),直线上的点就可以表为 \(A+\bm vt\),限制 \(t\) 可以得到线段或射线 .

点到直线的距离:

  1. 文化课知识:\(P(x_0,y_0),\ \ell:ax+by+c=0\),距离:

    \[\operatorname{dist}(P,\ell)=\dfrac{|ax_0+by_0+c|}{\sqrt{a^2+b^2}} \]

  2. 叉积算出平行四边形面积然后除以底 .

线段相交:

  • 跨立实验:两端点在另一条直线的两侧(叉积判断).
  • 需要特殊处理共线情况 .

求交点:解方程 .

特殊情况(三点共线、四点共圆)在某些情形下可以直接扰动解决 .

POJ 3304 Segments

给 \(n\) 条线段,问有没有一条直线,满足这些线段在直线上的投影有公共点 .

\(n\le 100\) .

Solution

考虑找一条过所有线段的直线然后画一条与其垂直的线就好了 .

只需要连每两个线段端点然后判断即可找到一条过所有线段的直线 .

需要特判 \(n=1\) .

时间复杂度 \(O(n^3)\) .

POJ 2826 An Easy Problem?!

给两块长度相等的板子,天上垂直落下雨滴,问最后接到多少水 .

Solution

就是找到线段最高点连一下算三角形面积,有一个重要边界情况需要特殊处理:

多边形基础

多边形:用顶点表示 .

简单多边形面积:三角剖分,答案等于相邻边叉积和的一半 .

简单多边形重心:三角剖分,三角形是平凡的,然后合并就行了 .

点和多边形的位置关系(PIP):从点出发引一条射线,判断交点奇偶性,可能需要多引几条规避边界问题 .

凸包

凸包就是最小的包含所有给定点的凸多边形 .

\([0,n]^2\) 上整点凸包点数上界:\(O(n^{2/3})\),证明细节可参考杨景钦 2017 年集训队论文 .

Andrew 算法

单调栈处理即可 .

详细说明 .

动态凸包

动态凸包:带插入删除维护凸包信息 .

每次插入只会改 \(O(1)\) 个点,删除必须先插入,所以维护凸包的结构复杂度均摊下来是没有问题的 . 只需要用平衡树状物维护上下凸壳就可以了 .

练习题(板子):

半平面交

半平面:一条直线一侧的位置 .

凸包和半平面交是对偶问题,所以做法也是基本相似的 . S&I 算法:极角排序后单调栈维护 .

HNOI2012 射箭

有若 \(n\) 条竖着的线段 \(x=x_0,\ y\in[y_1,y_2]\) 组成序列 \(\{a\}\),画一个过原点的抛物线问过的线段和线段序列 \(\{a\}\) 的 LCP 最长是多少 .

\(n\le 10^5\) .

Solution

起手二分,那么一条抛物线 \(y=ax^2+bx\) 过 \(x=x_0,\ y\in[y_1,y_2]\) 当且仅当:

\[\dfrac{y_1}{x_0}\le ax_0+b\le\dfrac{y_2}{x_0} \]

不等号两个方向分别是一个半平面,跑半平面交判断即可 .

Minkowski 和

定义:两个凸包 \(A,B\) 的 Minkowski 和 \(C=\{a+b\mid a\in A,b\in B\}\) .

就是相当于对于凸包 \(A\) 沿着 \(B\) 的每个向量移动后得到的所有位置的并 .

做法不是很困难,极角排序后归并就行了 . 如果有三点共线情况还需要再求一次凸包 .

JSOI2018 战争

给两个凸多边形 \(A,B\),若干次操作,每次将 \(B\) 平移一下,操作后问 \(A,B\) 是否有交 .

\(A,B\) 的点数和操作次数均不大于 \(10^5\) .

Solution

设 \(A,B\) 上有点 \(a,b\),那么移动向量 \(\bm v\) 满足有交当且仅当存在 \(b+\bm v=a\) .

可以写成 \(\bm v=a-b\),Minkowski 和算 \(A+(-B)\) 就行了 .

杂项

三维计算几何部分我就不写了 .

Pick 定理

顶点均为整点的简单多边形,面积 \(A\)、内部格点数和边上格点数满足 \(A=i+\frac b2-1\) .

最小圆覆盖

最小圆覆盖:平面上若干个点,找一个最小的圆包含所有点 .

暴力:枚举三个点 \(i,j,k\) 组成一个圆,两个点 \(i,j\) 作为直径组成一个圆 .

优化:目前枚举到的点不能在最优圆内 .

然后随机打乱复杂度就对了 .

平面最近点对

cdq 分治双指针,复杂度是 \(O(n\log n)\) 或者 \(O(n\log^2n)\) 的 .

关于复杂度可以发现的是某个点周围有用的点不会很多:

标签:直线,QAQ,cdot,Max,线段,凸包,多边形,几何,theta
From: https://www.cnblogs.com/CDOI-24374/p/17614518.html

相关文章

  • 计算几何模板
    namespaceComputationGeometry{constldeps=1e-8,pi=acosl(-1.0);//点/向量structvec{ldx,y;vec(ldX=0,ldY=0){x=X;y=Y;}//输入输出voidin(){scanf("%Lf%Lf",&x,&y);}voidout(){printf(&......
  • 【学习笔记】【数学】计算几何基础
    点击查看目录目录前置知识:叉积与跨立实验前置知识:建议虽然是简单的前置知识,还是打开略过一遍。浮点数与误差分析(少用除法)向量相关向量向量,就是带有方向和大小两个属性的边,通常形式为\(\overrightarrow{AB}=(a_1,a_2)=A\)。运算与性质:判等:两点坐标重合。ilint......
  • 苹果M3 Max有两种版本:14+40?还是16+40?
    最近有关苹果M3系列处理器的消息突然多了起来,包括M3、M3Pro、M3Max,都将升级为台积电3nm工艺,但规格上比较保守,至少核心数量不会大幅增加。此前说法称,M3Max将配备14个CPU核心、40个GPU核心,相比于M2Max都增加了2个。根据最新曝料,苹果正在测试两种版本的M3Max,其一就是14+40核心......
  • 计算几何の板子
    一精度处理\(eps\)和\(sgn\)constdoubleeps=1e-8;intsgn(doublex){//判断大小if(fabs(x)<eps)return0;elsereturnx<0?-1:1;}二点1点的初始化向量的表示形式上与点完全相同重载点运算符,支持向量的四种运算structPoint{doublex,y;Poi......
  • 凸优化9——强对偶条件、几何解释、影子价格
    中科大-凸优化笔记(lec31)-Lagrange对偶(三)_及时行樂_的博客-CSDN博客中科大-凸优化笔记(lec32)-几种解释_及时行樂_的博客-CSDN博客关于Slater条件的证明有点难,我觉得暂时先记住就好此外我关注了一下影子价格这个东西什么是影子价格?——线性规划的对偶解,及拉格朗日乘数-知乎(......
  • 【HMS Core】Health Kit 血压、血糖等数据返回数据包含max,min,avg,last 数据,这些数据
    ​【问题描述】1. 血压、血糖等数据返回数据包含max,min,avg,last数据,这些数据的含义是什么意思?​2. 如何获取用户上传健康数据的腕表的型号 【解决方案】1、血压原子采样统计数据类型开放的是多日统计查询接口,统计的维度是按照自然日进行统计的。​最大最小以及平均......
  • 【HMS Core】Health Kit 血压、血糖等数据返回数据包含max,min,avg,last 数据,这些数据
    【问题描述】1. 血压、血糖等数据返回数据包含max,min,avg,last数据,这些数据的含义是什么意思?2. 如何获取用户上传健康数据的腕表的型号【解决方案】1、血压原子采样统计数据类型开放的是多日统计查询接口,统计的维度是按照自然日进行统计的。最大最小以及平均值是指这一天的最大......
  • 26-Maxwell
    官网地址:http://maxwells-daemon.io/Maxwell是由美国Zendesk公司开源,使用Java编写的MySQL变更数据抓取软件。它会实时监控Mysql数据库的数据变更操作(包括insert、update、delete),并将变更数据以JSON的格式发送给Kafka、Kinesi等流数据处理平台。1.Maxwell工作原......
  • Sql去重查询数据,存在部分字段相同 max(id)  和 group by配合使用
    Sql去重查询数据原文链接:https://blog.51cto.com/u_15910936/5932613最近在工作过程中,面试过程中, 部分求职者或者同事,对sql怎么去重查询,不是太熟练今天下午忙里偷闲,整理了一下 其实sql基本的查询,还是蛮有意思,  下面是我大致整理的几种去重查询 1.存在2条一样的数据, 使......
  • 【230806-4】三角形ABC中,内角ABC的对边为abc,已知b=2,角B=45度。求:三角形ABC面积的最大
    ......