@2368860385
2020-11-07T03:00:26.000000Z
字数 2001
阅读 1022
前：day1上午——计算几何
衢州
2018.7.28
目录
Points and Segments
点到直线距离：叉积
两线段是否包含：所有点排序，在一条直线上。
格林公式
比较：
a>0 a>=eps
a>=0 a>=-eps
T1 Faster Than LightT1
一定在端点上，对与一个方格，找到可以覆盖它的四条线段。
T2 Pun
点集相似
重心 - 平移
最远点 - 缩放
最远点的序列 - 旋转
求出从一开始的字典序最小的序列。
Circles
外公切线：（画图表示）
内公切线：
T1 清华集训2016定向越野
求出所有的外公切线，内公切线，判断这些切线与园不相交，跑最短路。
n^3+最短路的复杂度。
T2 Kingdom Trip
每个点j，i可以转移的区域可以求出来：
上图中d=1，现在i合法的转移的区域就是两个圆的交。
Polygons
多边形
Minkowski sum
在两个给定的多边形里各取一点，组成向量，求向量集合。
将两个多边形的边，取出，然后按极角排序，依次放入线段，即：讲两个多边形的边加起来0。
平面区域
给一些线段，求构成的每个区域的面积。
每个点记录和，所在这条线段与下一条线段相交，的第一个点，从一个点出发，到下一个点就是一个平面区域的直线，左拐。
点定位
扫描线
T1 Enclosure
凸包切线，然后求出面积
T2 Circular Island
圆上找一条直线，把红点蓝点分开。
1、二分角度区间是否合法
求红点与蓝点合法区间的交。
2、求凸包，然后枚举红色凸包的点。
左边为红点凸包，H点和I点连边，但是不能E点，G点只能和C点，不能和J点。
T3 规避
平面上有若干个多边形障碍，求最短路。
和上面的定向越野一样，把圆的切线改成凸包切线。
T4 NOI2017 分身术
大小为n的点集，每次删除k个点询问剩下点凸包面积。
预处理：k层凸包，每个点向内找到切点。
删除一个点，讨论，之后的凸包是什么
T5 Random convexhull
给n个点，第i个点有pi的概率出现，求凸包的期望大小。
对于一条线段AB，它出现在凸包里的概率为：
，k为以AB非凸包一侧的点。下图中为
T8 Bear and Isomorphic Points
题解
对于一个点，求出它能移动的最大面积，不能跨过直线。
求半平面交。
一般这种半平面交题都是舍去一些直线然后做，这题也是类似。 可以用归纳法证明每个点只需要和极角序下他的下一个点和最后一个点（满足1在其同一侧）连线即可。
三维
三维向量变换
三维凸包
简单四面体的面积和有向面积
某区域赛F
给你两个三维旋转变换A,B，求单位球上的点p，在两个变换之后，距离最远。求出这个最远的距离。旋转以矩阵的形式给出。
1、线性代数法
设
设，为单位矩阵
为对称矩阵
根据一个什么定理，最大值为M的最大特征值。
如果求最小，即M的最小特征值。
2、
变换的逆还是一个变换。
HDU 5846
给一个三维凸包，每次给一个平面求交多边形的面积。
枚举三途凸包的每个棱，求与平面的交点，构成平面，求面积。
球面几何
经纬度坐标系
投影
answer=表面积/4
反演
每个点保持到反演中心的方向不变，到反演中心的距离变成r/dis
相当于做了一个导数。
反演两次不变
反演前后的关系的性质不变
过反演中心的圆 - 不过反演中心的直线
不过原点的直线 - 过原点的圆
四点共圆
反演后，三点共线，的数量。
放盘子
大圆是R1,中间的两个小圆是R2,R3
在R1中的，除了R2,R3的区域放圆，先放大的，问放到第n个的大小。
以B点为反演中心，那么R2,R3反演后是两条平行的直线，然后在两条直线中放圆。
问题现在放的圆实际的直径。
用HE，求出JI，不能用半径。
奇怪的题
分式线性变换
坑：
fwt
共轭
球面几何经纬度坐标系
分式线性变换
最小表示法
https://blog.csdn.net/qq_35776579/article/details/54836612
https://blog.csdn.net/clover_hxy/article/details/53966405
T2 Kingdom Trip
T2 Circular Island 第一个
某区域赛F
奇怪的题
