恙髡 发表于 2025-8-19 21:47:49

2025杭电多校第九场 乘法逆元、阿斯蒂芬、计算几何 个人题解

计算几何

计算几何

题目


思路

由于给定的是一条不自交的折线，因此可以直接沿着给定的折线来走
如果下一个点相对于当前的前进方向是向左，那么当前点标记为1，否则为0
判断方向可以通过相邻的两个线段的向量的叉乘正负性
最后根据给定的折线是顺时针还是逆时针来判断1、0对应的是\(YES,NO\)
如何判断给定的折线是顺时针还是逆时针呢？
可以对相邻的两个点的向量进行叉乘后累加，计算这个多边形的面积，最后判断总面积的正负形就可以知道给定的折线是顺时针还是逆时针了
特别需要注意的是，由于给定的点都是整数，叉乘计算出来的数也是整数，如果用板子里自带的\(double\)类型的变量和函数，将会出现精度问题！！
赛时因为这个问题\(WA\)了8发
代码实现

#include#include#include#include#include#includeusing namespace std;using ll = long long;#define rep(i, a, b) for(int i = (a); i = (b); i --)#define see(stl) for(auto&ele:stl)cout

况雪柳 发表于 2025-10-14 00:43:04

谢谢分享，辛苦了

左优扬 发表于 2025-10-20 14:05:29

东西不错很实用谢谢分享

诸婉丽 发表于 2025-11-12 19:04:56

前排留名，哈哈哈

命煦砌 发表于 2025-12-15 18:59:36

新版吗？好像是停更了吧。

甦忻愉 发表于 2025-12-23 20:43:16

感谢，下载保存了

利怡悦 发表于 2026-1-1 21:32:22

谢谢分享，试用一下

赊朗爆 发表于 2026-1-11 15:38:53

感谢分享，学习下。

俏挺喳 发表于 2026-1-12 23:33:40

谢谢分享，试用一下

况雪柳 发表于 2026-1-15 01:58:23

很好很强大我过来先占个楼 待编辑

焦尔蕾 发表于 2026-1-16 08:51:49

喜欢鼓捣这些软件，现在用得少，谢谢分享！

叟澡帅 发表于 2026-1-18 09:50:06

yyds。多谢分享

涅牵 发表于 2026-1-19 02:00:15

感谢分享

馏栩梓 发表于 2026-1-26 04:18:49

谢谢楼主提供！

林鱼 发表于 2026-1-26 09:19:42

感谢，下载保存了

呼延含玉 发表于 2026-1-28 06:15:53

yyds。多谢分享

欧阳梓蓓 发表于 2026-1-28 08:29:39

不错，里面软件多更新就更好了

尹疋 发表于 2026-1-30 05:20:44

感谢分享

剧拧并 发表于 2026-2-3 06:54:52

感谢，下载保存了

赏听然 发表于 2026-2-3 11:02:03

用心讨论，共获提升！
页: [1] 2 3
查看完整版本: 2025杭电多校第九场 乘法逆元、阿斯蒂芬、计算几何 个人题解