本贴针对的方法:极角排序法。
目前发现两种避免此测试点第五个输出 WA 掉的办法。
- 增加排序关键字法
inline bool operator<(const Point sec) const {
return ang < sec.ang;
}
改成:
inline bool operator<(const Point sec) const {
if (!cmp(ang, sec.ang)) {
return x < sec.x;
}
return ang < sec.ang;
}
对于本题而言,二关键字为 y 就不行,数据就很迷。
- 原点偏移法
给原点一个增量:
const double PI = acos(-1);
const double SQRT2 = sqrt(2);
Point o{x: PI / 100.0, y: SQRT2 / 100.0, ang: 0.0};
注意增量不要给太多了。