对比判断点是否在凸包内的二分极角法 O(log n) 与绕数法 O(n) 的取舍？
二分极角法：以凸包内某参考点（如凸包左下角点）为基点，把其他顶点按极角排序，查询点也按极角二分定位所在扇形，再判断与对应边的叉积关系，O(log n) 判定。需凸包已按极角排序且参考点确定。绕数法（或射线法）：从查询点发出射线，统计与多边形边的交点/绕数，O(n) 判定，适用于任意多边形（不必凸）。取舍：若凸包多次查询，用 O(log n) 二分法；若单次查询或任意多边形，用 O(n) 绕数法。
二分法利用凸包极角单调性把查询降到对数；绕数法通用但线性。多次查询时对数优势明显，是"预处理换查询速度"的经典权衡。
说明叉积与点积的几何意义，以及用叉积判断转向、点积判断投影方向、鞋带公式求面积？
叉积 (b-a)×(c-a) 的符号表示三点 a,b,c 的转向：正为逆时针（左转），负为顺时针（右转），零为共线；也用于判断点 c 在直线 ab 的哪一侧。点积 (b-a)·(c-a) 反映投影方向：正表示 c 在 ab 方向上有正向投影，负为反向，用于判断点相对线段的位置。鞋带公式 A = 1/2 |Σ (x_i·y_{i+1} - x_{i+1}·y_i)| 求多边形面积，本质是各边叉积的累加，对有向多边形自动处理符号。
叉积给方向、点积给投影，是计算几何的"手"与"眼"。鞋带公式把多边形面积分解为三角形叉积之和，是叉积最直接的面积应用。
long cross(int ax,int ay,int bx,int by,int cx,int cy){ // 向量 ab × ac
return (long)(bx-ax)*(cy-ay) - (long)(by-ay)*(cx-ax);
}
double area(int[][] p) { // 鞋带公式
double s = 0; int n = p.length;
for (int i = 0; i < n; i++) {
int j = (i+1)%n;
s += (long)p[i][0]*p[j][1] - (long)p[j][0]*p[i][1];
}
return Math.abs(s)/2.0;
}
解释最近点对分治的合并步为何只需检查分割线两侧常数个点（鸽笼原理），以及按 y 排序如何避免 O(n²) 退化？
分治求最近点对：左右递归各得最近点对距离 d，合并时只需考虑分割线两侧距离 ≤ d 的带内点。对带内点按 y 排序，对每个点只需检查其上方 y 距离 ≤ d 的点。由鸽笼原理，若边长 d 的方形内有超过常数个点，则其中必有两点距离 < d（否则最多约 8 个点能放入 d×d 方格两两距离 ≥ d），故每个点只需检查常数个（≤7）后继点。总复杂度 O(n log n)。不加 y 排序直接两两比较会退化 O(n²)。
鸽笼原理决定了在 d×d 区域内只能容纳常数个彼此距离 ≥ d 的点，从而保证合并步线性（每点常数次比较）。按 y 排序使检查集中在"可能更近"的邻近点，是防止退化的关键。
对比 Andrew 单调链与 Graham Scan 的凸包算法，说明为何都是 O(n log n)，以及 Andrew 如何避免浮点极角比较？
Andrew 单调链：先按 x（相等则按 y）排序，分别构造上凸壳与下凸壳，用叉积判断弹出栈顶，合并得凸包。Graham Scan：先取最低点作参考，按极角排序，再扫描维护凸包。两者都 O(n log n)，排序主导（扫描本身 O(n)）。Andrew 的优势：用 x 排序 + 叉积比较，避免 atan2 的浮点极角计算与精度问题，叉积是整数运算（若坐标整数）更稳定，且共线点处理更可控。
复杂度来自排序，扫描线性。Andrew 用单调坐标排序规避浮点极角，是竞赛中更稳的选择；Graham 的 atan2 在接近共线时易因浮点误差出错。
// Andrew 单调链：pts 需按 x 优先排序
long cross(int[]o,int[]a,int[]b){ return (long)(a[0]-o[0])*(b[1]-o[1])-(long)(a[1]-o[1])*(b[0]-o[0]); }
List<int[]> andrew(int[][] pts){
int n=pts.length; java.util.Arrays.sort(pts,(p,q)->p[0]!=q[0]?p[0]-q[0]:p[1]-q[1]);
int[] h=new int[2*n]; int k=0;
for(int i=0;i<n;i++){ while(k>=2&&cross(pts[h[k-2]],pts[h[k-1]],pts[i])<=0)k--; h[k++]=i; }
for(int i=n-2,t=k+1;i>=0;i--){ while(k>=t&&cross(pts[h[k-2]],pts[h[k-1]],pts[i])<=0)k--; h[k++]=i; }
List<int[]> res=new java.util.ArrayList<>();
for(int i=0;i<k-1;i++)res.add(pts[h[i]]);
return res;
}
对比 Graham Scan 与 Andrew 单调链的排序与扫描过程，说明复杂度为何 O(n log n)？
Graham Scan：先找最低点（y 最小）为参考，对其余点按极角排序，然后从参考点出发扫描，用叉积判断是否弹出栈顶保持左转，O(n log n)。Andrew 单调链：按 x/y 排序，分别构造上下凸壳，各扫描一次，O(n log n)。两者扫描均 O(n)，总复杂度由排序 O(n log n) 主导。差别：Graham 用极角排序（atan2 或象限比较），Andrew 用坐标排序 + 叉积，Andrew 更易避免浮点误差。
排序是两者共同瓶颈，扫描线性。选择取决于是否介意浮点极角：Andrew 用整数叉积更稳，成为竞赛首选。
说明线段相交判定方法，并解释分治法求最近点对的复杂度为何为 O(n log n)？
线段相交判定用两线段各自的"跨立测试"：对每条线段，检查另一条线段的两个端点是否分居其两侧（叉积符号），加上共线时的边界处理。分治求最近点对：按 x 排序，中点分割，左右递归，合并时检查带内点并按 y 排序比较常数个邻近点。合并 O(n)，递归 T(n)=2T(n/2)+O(n)，得 O(n log n)。交叉比较部分因鸽笼原理每点常数次，故总体对数。
合并步的 O(n) 与鸽笼原理保证的常数比较是 O(n log n) 的关键。若无 y 排序直接两两比较会 O(n²)。
说明极角排序为何用象限加叉积代替 atan2，以及共线点如何稳定排序？
用 atan2 计算极角再进行排序会引入浮点误差，且当角度接近相等时可能排序错误。改进：先按象限（第一、二、三、四象限）分块，象限不同则按象限排序，同象限内用叉积 sign(cross(a,b)) 判断极角大小：cross(a,b)>0 表示 b 在 a 的逆时针方向，即 a 的极角更小、应排在 b 前面，实现精确整数比较。共线点（cross=0）时按距离排序（如按到参考点距离升序），保证稳定且不破坏凸包构造。
叉积是整数精确运算，避免浮点；象限划分让比较器有意义且高效。共线时按距离排序避免后续凸包算法对共线点的处理歧义。
int half(int[] p){ return p[1]>0? (p[0]>0?1:2) : (p[1]<0? (p[0]<0?3:4) : (p[0]>0?1:3)); }
int cmp(int[] a,int[] b){ int ha=half(a),hb=half(b); if(ha!=hb)return ha-hb;
long c=cross(a,b); if(c!=0)return c>0?-1:1; return Long.compare(len2(a),len2(b)); }
说明点到线段的最短距离计算，投影参数 t 如何钳制在 [0,1]，以及它在退化情形与点到直线距离的区别？
设线段端点 A、B，点 P，先算投影参数 t = ((P-A)·(B-A)) / |B-A|²，它表示 P 在 AB 方向上的投影位置。若 t∈[0,1]，垂足在线段内，最短距离为 |P-(A+t(B-A))|；若 t<0，最近点为 A；若 t>1，最近点为 B。即把 t 钳制到 [0,1]。与点到直线距离区别：点到直线不限 t，直接取垂足；点到线段则需考虑端点。退化情形：当 A=B（线段长为 0）时 |B-A|²=0，分母为零，需特判直接返回 |P-A|。
钳制 t 是"投影位置是否落在线段内"的关键。退化时提前判断避免除零，是数值鲁棒性的基本要求。
说明半平面交如何用排序+双端队列在 O(n log n) 求解，以及"留左去右"的淘汰逻辑？
半平面交求所有半平面的交集（可能为凸多边形、线段、点或空）。算法：把每条半平面按其直线方向向量按极角排序（同角保留更靠左的），用双端队列维护当前交集边界。插入新半平面时，若队列尾部两条直线交点在新半平面右侧（不满足），则弹出尾部；头部同理。最终队首尾交点构成凸多边形。O(n log n) 由排序主导，队列操作为 O(n)。"留左去右"即只保留满足"左半平面"条件的交点，淘汰落在右侧的边界。
双端队列使头部与尾部都能弹出，配合极角排序保证交集的凸性。这是计算凸多边形交/可达区域的经典 O(n log n) 算法。
说明凸包与 Voronoi 图、Delaunay 三角剖分的对偶关系，以及 Delaunay 边翻转与凸包下包络的关系？
Voronoi 图把平面划分成离各点最近的区域，Delaunay 三角剖分是其对偶图（相邻 Voronoi 单元对应的点连边）。Delaunay 三角剖分满足空圆性质（每个三角形的外接圆内不含其他点）。它与凸包的联系：把点提升到抛物面 z=x²+y² 上，Delaunay 三角剖分对应这组点的凸包的下包络（lower hull）在平面的投影。因此 Delaunay 边翻转（保持空圆性质）等价于维护抛物面凸包的下包络，可借助凸包算法计算 Delaunay。
提升到三维抛物面是 Delaunay 与凸包互通的桥梁。下包络性质保证空圆条件，从而把三角剖分问题归约为凸包问题。
说明用凸包+旋转卡壳求最大面积三角形的方法与复杂度？
最大面积三角形的三个顶点必在凸包上（若某顶点在凸包内部，可向外移动增大面积）。对凸包上每对顶点作为底边，用旋转卡壳找离该底边最远的顶点（面积最大），随底边旋转，最高点单调移动，故每条底边 O(1) 摊销。枚举所有底边 O(n²)，总 O(n²)。此方法比枚举三个点 O(n³) 更优。
关键是"底边固定时最高点随底边单调旋转"的旋转卡壳性质，使枚举底边时最高点不用每次重扫。面积最大问题在凸包上线性化顶点数据。
说明 Lloyd 松弛（k-means 交替迭代）的收敛性，为何单调不增但只能收敛到局部最优？
Lloyd 松弛（k-means）交替执行：分配步（把每个点归到最近质心）与更新步（把每个质心移动到其簇的平均点）。两步都使目标函数（到质心距离平方和）单调不增：分配步每点选最近质心降目标，更新步用平均点使簇内距离平方和最小（均值是最优解）。因此目标函数单调递减。但每步只做局部最小化，非凸目标函数（多个质心耦合）存在多个局部最优，算法可能停在局部最优而非全局最优，且依赖初始质心。
单调性来自"坐标下降"框架：每步对一组变量精确最小化。但整体非凸，故只能保证局部收敛。这是 k-means 对初始值敏感并被多次重启的原因。
说明旋转卡壳除凸包直径外的其他应用：凸包间最近距离、宽度？
旋转卡壳在凸包上的其他应用：凸包间最近距离——对两个凸包分别维护一对对踵点，旋转时更新最近距离；宽度（宽带/最小宽度）——凸包的两条平行支撑线间的最小距离，通过旋转卡壳沿对踵点对扫描，等价于求所有对踵点对距离的最小值（或用于求最小外接矩形的高）。这些应用都利用"对踵点对随旋转单调变化"的性质，O(n) 完成。
旋转卡壳的核心是"对踵点对单调性"，使众多极值问题（直径、宽度、最近距离、最小外接矩形）都能在 O(n) 内求解。
说明旋转卡壳如何在 O(n) 内求凸包直径（最远点对），及对踵点对的单调旋转过程？
凸包直径（最远点对）必是对踵点对（可被两条平行线支撑的多边形顶点对）。旋转卡壳：从某条边开始，维护当前对踵点对，用叉积判断"下一个顶点是否使面积更大"来推进指针，使对踵点对随边的旋转单调地沿凸包前进。每个顶点作为对踵点只会被访问常数次，故总 O(n)。不断更新两顶点距离最大值即直径。
对踵点对的单调性保证每个顶点摊销常数次访问，避免 O(n²)。这是旋转卡壳能用 O(n) 求多类极值问题的根源。
说明最小圆覆盖中三点共线/重合等退化情形的数值处理，保证工程鲁棒性？
Welzl 算法递归：若三点确定唯一圆，则用三点外接圆；若三角形退化（三点共线或重合），则不能用外接圆公式（可能除零或圆半径无穷大）。处理：三点共线时，唯一的圆是"过最远两端点的直径圆"；点重合时圆退化为点。工程上需用 EPS 判断共线（叉积绝对值 < EPS），分情况处理：三点共线→直径圆，两点重合→两点圆，重合太多→点圆。同时外接圆公式含分母，需判零并避免除零。
退化情形是计算几何鲁棒性的关键。用 EPS 判断共线/重合，并分派到直径圆/点圆等退化圆，避免公式除零与错误结果。
说明最小圆覆盖的 Welzl 随机增量算法及期望线性时间的证明思路？
Welzl 算法：随机打乱点集，逐个加入，维护当前点集的最小圆。若新点已在外接圆内则跳过；否则新点必在最小圆边界上，递归构造"过该点的最小圆"。递归中最多 3 个边界点确定圆（2 点确定直径圆，3 点确定外接圆）。期望线性时间：因为随机顺序下，每个点落在当前圆边界上的概率为 O(1/k)（边界点 ≤3 个中之一），故期望的"重算次数"累积为线性。总体期望 O(n)，最坏 O(n³) 但随机化使其几乎不出现。
关键是"每个点被选为边界点的概率小"，从而重算开销累积为线性。随机化避免最坏输入，是"随机增量"的典型价值。
说明最小外接矩形为何至少有一条边与凸包某条边共线，以及旋转卡壳 O(n) 实现？
最小面积外接矩形至少有一条边与凸包的某条边共线（重合）：若矩形四条边都不与凸包边共线，可微旋转矩形使某凸包边与矩形边对齐，同时面积不增（可通过支撑线论证），故最优矩形必贴合一条凸包边。旋转卡壳：枚举凸包每条边作为矩形的一条边，用旋转卡壳维护其余三条支撑线（上、左、右），每次 O(1) 摊销，总 O(n) 求最小面积。
"贴合凸包边"把连续无穷的矩形位置离散为 n 个候选（每条凸包边一个），从而可枚举。旋转卡壳让每条边对应的四条支撑线单调推进，O(n) 完成。
说明点在多边形内判断的射线法/转角法原理及浮点精度处理？
射线法：从点 P 向任意方向发射线，统计与多边形边的交点个数，奇数在内部，偶数在外部。转角法（绕数法）：计算多边形绕 P 点累计的角度/绕数，绕数次非零则在内部。浮点精度处理：判断交点时用叉积/符号比较，避免精确相等；点在边上时需特判（用 EPS 判断叉积绝对值 < EPS 视为共线点）；射线过顶点、共用顶点等边界情况要统一规则（如只统计"上"半边的交点），避免重复计数。用整数坐标时可完全避免浮点。
射线法简单高效，但顶点/边上的边界情形需规则化避免歧义；转角法更稳健但需浮点/ACOS 精度。工程上常以 EPS 阈值处理共线，且射线法用"半开区间"约定处理顶点。
说明高维凸包的复杂度随维度上升的原因，以及竞赛为何只处理二维？
d 维凸包的顶点/面数在最坏情况下可达 O(n^{⌊d/2⌋})（如 d=3 时 O(n)，d=4 时 O(n²)），这是上界定理（upper bound theorem）的结果。高维凸包不仅面数爆炸，算法也更复杂（增量法、计算量随维度指数增长），d 维凸包的面数随维度快速上升使得存储与构造都不可行。竞赛中通常只处理二维（凸包顶点 O(n)、算法成熟简单），少数处理三维，更高维几乎不出现。
上界定理指出固定维 d 下凸包复杂度 O(n^{⌊d/2⌋})，随 d 面数增长。竞赛以二维为主，因为二维凸包算法简单、复杂度线性且浮点误差可控。
说明计算几何中叉积判断方向时如何用 EPS 处理共线，避免浮点误差？
计算几何中叉积结果用于判断方向，但浮点运算引入微小误差，直接比较叉积是否为 0 会误判共线。处理：用 EPS 阈值，当 |cross| < EPS 视为共线（方向为 0），为正视为逆时针，为负视为顺时针。EPS 取值需与坐标量级匹配（常用 1e-9 或 1e-8）。同时避免使用精确相等的 double 比较，改用带 EPS 的符号判断。若坐标全为整数，可用长整型叉积完全避免浮点误差。
EPS 是"浮点容差"的工程化：把绝对零扩展为带容差的区间。选择合适 EPS 与量级匹配是关键，过大误判共线、过小仍受误差影响。
static final double EPS = 1e-9;
int sgn(double c){ return Math.abs(c) < EPS ? 0 : (c > 0 ? 1 : -1); }
说明扫描线求矩形面积并的原理，离散化 x 坐标后用线段树维护覆盖次数，为何复杂度 O(n log n)？
扫描线求矩形面积并：把所有矩形的上下边按 y 排序，用一条水平线从下往上扫描；对每段 y 区间，用线段树维护"当前被覆盖的 x 区间总长度"，面积累加 = 高度差 × 覆盖 x 长度。为离散化，把 x 坐标去重排序作为线段树叶子区间，线段树每节点维护该区间被覆盖次数 cnt 与覆盖长度 len。每处理一条边更新线段树（区间加/减覆盖次数），O(log n)。共 2n 条边，总 O(n log n)。
离散化 x 把连续区间压缩到 O(n) 个断点，线段树支持区间覆盖次数的增减并查询覆盖总长度，使每条边 O(log n)。这是区间覆盖类几何问题的标准解法。