计算几何 练习记录

点击量：1560

简单题目

POJ 2318 TOYS

题目链接 代码

对于一条线，它的上端点为 $A$，下端点为 $B$，如果 $\overrightarrow{CA}\times \overrightarrow{CB}>0$，说明点 $C$ 在 $AB$ 的右侧，否则在 $AB$ 左侧。并且由于点不在线上，所以不会出现 $=0$ 的情况。二分即可。

HDU 4709 Herding

题目链接 代码

数据范围比较小，可以枚举三个点，用叉积算出三角形面积，特判掉 $0$ 即可。

洛谷 P1183 多边形的面积 HDU 2036 改革春风吹满地

题目链接1 代码 题目链接2 代码

按逆时针顺序三角剖分。注意 $n$ 和 $0$ 的联系，最后要除以 $2$。

POJ 2398 Toy Storage

题目链接 代码

这题和TOYS那个题基本一致，坑点在于要看懂输出格式，以及隔板给出的顺序并非升序，需要进行排序。

凸包相关

UVA 11626 Convex Hull

题目链接 代码

“送分题”写麻烦了。凸包上的点都给你找好了，只需要以凸包内一点为原点，对所有点进行极角排序即可。为了保证是凸包内一点，可以找横坐标（相同情况下纵坐标）最小的点 $(x+10^{-2},y+10^{-2})$，因为所有点都是整点。最后再加回来就好了。

不过感觉写个凸包会稳一些。

UVA1303 Wall

题目链接 代码

求凸包再加上一个 $2\pi L$ 即可。

洛谷 P3829 [SHOI2012]信用卡凸包

题目链接 代码

和Wall很像的一道题，需要预处理出点的坐标。（把加周长想成加面积了应该怎么爆炸 等，在线急）

线段相交

UVA 393 The Doors

题目链接 代码

线段相交简化版，甚至特判+枚举就可以过（我当然是这样过的了 _{（BTW，洛谷 P1354 房间最短路问题 有双倍经验）}

洛谷 P4361 [SHOI2015]激光发生器

题目链接 代码

多次判断相交。注意法向量的方向，需要分类讨论。

半平面交

洛谷 P2600 [ZJOI2008]瞭望塔

题目链接 代码

直接求所有线段的左侧半平面交。但是注意瞭望塔是可以不建在拐点处的，所以在中间要算交点，在两边要特判，防止出现负数。