166b专题

[Codeforces 166B] Polygons (点在凸多边形内)

Codeforces - 166B 判断任意多边形 B是否严格在凸多边形 A内部 点在凸多边形内部试板题 如果 B的所有顶点在 A内,则 B在 A内 由于 A的顶点有 105 10^5个,B的顶点有 104 10^4 个 所以不能用 (n) \mathcal{O}(n)的暴力判断 有一个 (logn) \mathcal{O}(logn) 的二分做法 基本原理是用