核心概述：用射线交数与边界判定判断点是否在多边形内，时间 O(n)，strict 控制边界是否算作内部。
Description: Returns true if p lies within the polygon. If strict is true, it returns false for points on the boundary. The algorithm uses products in intermediate steps so watch out for overflow. Time: O(n) Usage: vector
v = {P{4,4}, P{1,2}, P{2,1}}; bool in = inPolygon(v, P{3, 3}, false); Status: stress-tested and tested on kattis:pointinpolygon
展开阐述：
-
定义与背景
- 任务：判断给定点 a 是否位于简单多边形 p 的内部（或内部+边界）。
- 场景：点选命中测试、几何布尔运算中的原子查询、GIS 点落区判断、025-几何-凸包/042-几何-多边形面积等基础模块的配套判定。
- 接口（据实现）：
- template
bool inPolygon(vector & p, P a, bool strict = true)
- p 为多边形顶点序列，a 为待测点；strict=true 时边界点返回 false，否则 true。
- template
-
核心算法流程（射线法 + 边界检测）
- 边界检测优先：
- 对每条边 (p[i], q=p[(i+1)%n])，若 a 在该线段上，则直接根据 strict 返回：
- strict true → 返回 false；strict false → 返回 true。
- 对每条边 (p[i], q=p[(i+1)%n])，若 a 在该线段上，则直接根据 strict 返回：
- 射线交数：
- 取从 a 水平向右的射线，统计其与多边形边的“向上穿越”次数的奇偶。
- 代码等价表达：cnt ^= ((a.y < p[i].y) - (a.y < q.y)) * a.cross(p[i], q) > 0
- 仅在边跨越 a 的水平线且 a 位于边的左侧（由叉积符号给出）时翻转计数。
- 返回 cnt 的奇偶：奇数为内，偶数为外。
- 边界检测优先：
-
复杂度与边界条件
- 复杂度：逐边扫描 O(n)。
- 顶点落在水平线上：公式通过严格不等与差分避免“双计一次”。
- 边界点：通过第一步 onSegment 显式处理，避免与射线统计冲突。
- 自交多边形：该实现假设简单多边形，自交时“内部”定义不再唯一，结果未定义。
- 坐标数值：
- 中间乘法/叉积可能溢出，尤其 P=Point
大坐标时，需注意使用更大精度（如 __int128_t）或 long double。
- 中间乘法/叉积可能溢出，尤其 P=Point
-
实现细节与常见坑
- onSegment 的稳健性：整数几何可用方向与范围联合判定；浮点几何可用 segDist(a, segment) ⇐ eps。
- 水平/垂直边处理：无需特判，交数公式已通过高度比较与叉积统一涵盖。
- 顶点穿越消歧：((a.y < p[i].y) - (a.y < q.y)) 保证仅在“上跨或下跨”之一计数，不重复。
- 多边形方向：无要求；射线法对 cw/ccw 均适用。
-
变体与扩展
- 奇偶规则 vs. 绕数规则：本实现为奇偶规则；若需区分洞或方向，可改用绕数（累计角度）法。
- 圆/线段与多边形的相交测试：可结合020-几何-圆与直线相交、048-几何-线段相交扩展为更通用的裁剪/布尔运算。
- 凸多边形特解：若 p 为凸多边形，可用二分/方向测试在 O(log n) 判定。
-
正确性要点与不变式
- 边界先判定，保证不被射线统计二义覆盖。
- 射线与边的“规范穿越”定义确保奇偶不受水平边/顶点接触的干扰。
- 对简单多边形，奇偶规则与几何直觉一致。
-
对比与取舍
- 与绕数法：射线法实现更短、更快；绕数法可提供带符号的内外信息（依多边形方向）。
- 与点在凸包内（041-几何-点在凸包内）：凸多边形可 O(log n)；通用多边形射线法 O(n)。