一些常见的计算几何。
「HDU1756」Cupid’s Arrow
链接
题解
此题就是判断点是否在多边形内，采用射线法，时间复杂度 $O(n)$。
判断点在直线上
设点为 $P$，直线为 $AB$，若 $\vec{PA} \times \vec{PB} = 0$ 则 $P$ 在直线 $AB$ 上。
判断点在线段上
先判断 $P$ 是否在直线 $AB$ 上，然后判断 $P$ 是否在 $AB$ 端点构成的矩形范围内。
1 | inline bool isPointOnSegment(const Point &a, const Point &b, const Point &p) { |
射线法
平行于 $x$ 轴射出一条线，若与多边形有交点，则 cnt++，若 cnt 为奇数，那么点在多边形内。
代码
1 | /******************************************************************************* |
「POJ1269」Intersecting Lines
链接
题解
先判断直线平行，在判断共线，否则求交点。
判断平行
$\vec{AB} \times \vec{CD} = 0$ 则两直线平行。
判断共线
在平行的基础上，任意交换一个端点，叉积仍为 $0$ 则两直线共线。
求交点
设交点为 $P$，则 $P = A + \vec{AB} \cdot \frac {S_{ACD}} {S_{ACBD}}$，
1 | struct Line { |
代码
1 | /******************************************************************************* |
「POJ 3907」Build Your Home
链接
题解
就是求多边形的面积。
求多边形面积
相邻两点叉积求和，绝对值除以 $2$ 即为多边形的面积。
代码
1 | /******************************************************************************* |
「POJ 2318」TOYS
链接
题解
求落在每个区域内的点的个数，二分，然后用叉积判断位置即可。
代码
1 | /******************************************************************************* |
「POJ 3304」Segments
链接
题解
暴力枚举，然后判断线段与直线是否相交即可。
判断线段与直线是否相交
设直线为 $AB$，线段为 $CD$，若 $(\vec{AB} \times \vec{AC}) \times (\vec{AB} \times \vec{AD}) \leq 0$，则 $AB$ 与 $CD$ 相交。
代码
1 | /******************************************************************************* |
「POJ 1066」Treasure Hunt
链接
题解
就是判断线段与线段是否相交的问题。
判断线段与线段相交
首先是快速跨立实验，
$$max(A.x, B.x) \geq min(C.x, D.x)$$ $$max(A.y, B.y) \geq min(C.y, D.y)$$ $$max(C.y, D.y) \geq min(A.y, B.y)$$ $$max(C.y, D.y) \geq min(A.y, B.y)$$，
然后再判断
$$(\vec{AB} \times \vec{AC}) \times (\vec{AB} \times \vec{AD}) \leq 0 && (\vec{CD} \times \vec{CB}) \times (\vec{CD} \times \vec{CA}) \leq 0$$
代码
1 | /******************************************************************************* |
「POJ 1039」Pipe
链接
题解
题意就是从前面一段过来的光线，问最远可以射到哪，只能直射。
最远的那条光线肯定过一个上端点和一个下端点，所以我们枚举两个点，然后判断求交点。
注意精度
代码
1 | /******************************************************************************* |
「POJ 3348」Cows
链接
题解
答案就是凸包的面积除以 $50$，直接用 andrew 算法就可以了。
代码
1 | /******************************************************************************* |
「POJ 2187」Beauty Contest
链接
题解
就是裸的旋转卡壳。
代码
1 | /******************************************************************************* |
「POJ3335」Rotating Scoreboard
链接
题解
求多边形的核是否为空，直接半平面交就好了。
代码
1 | /******************************************************************************* |
「POJ3130」How I Mathematician Wonder What You Are!
链接
题解
同上，求多边形的核，半平面交即可 (这数据范围已无力吐槽，$n^2$ 都随便过啊….)
话说 PKUSC 怎么就考了这个题啊……
代码
1 | /******************************************************************************* |
「HNOI2007」最小矩形覆盖
链接
题解
首先有这样一个结论:
最小矩形中有一条边在凸包的边上。
否则可以旋转一个角度让面积变小。
我们逆时针枚举一条边，用旋转卡壳维护此时最左，最右，最上的点。
对于最上的点利用叉积计算面积来维护，对于左右点，其点积是在其对应边的投影与此边的乘积，所以我们可以通过点积来维护。
注意：第一次找卡壳，需要特判最左点。
此题 SPJ 似乎又被 Hack 掉了
代码
1 | /******************************************************************************* |
