计算几何 练习记录

作者: wjyyy 分类: 解题报告,计算几何,记录 发布时间: 2018-12-11 15:26

点击量:757

简单题目

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]瞭望塔

题目链接 代码

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

2
说点什么

avatar
2 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
Mayflyyh Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
Mayflyyh
游客

TQL

trackback

[…] 我的计算几何做题记录 可供参考 […]

/* */