给 WA on #52 的同学一点建议
查看原帖
给 WA on #52 的同学一点建议
392727
rsdbk_husky楼主2022/1/19 10:46

本贴针对的方法:极角排序法。

目前发现两种避免此测试点第五个输出 WA 掉的办法。

  1. 增加排序关键字法
	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 就不行,数据就很迷。

  1. 原点偏移法

给原点一个增量:

const double PI = acos(-1);
const double SQRT2 = sqrt(2);
// ...
Point o{x: PI / 100.0, y: SQRT2 / 100.0, ang: 0.0};

注意增量不要给太多了。

2022/1/19 10:46
加载中...