计算几何 练习记录

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

点击量:68

简单题目

POJ 2318 TOYS

题目链接 代码

    对于一条线,它的上端点为\(A\),下端点为\(B\),如果\(\vec{CA}\times \vec{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 房间最短路问题 有双倍经验)

1
说点什么

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

TQL

/* */