整个代码的思路和其他大佬是一样的
众所周知,使用double
会产生精度问题
一般情况下,我们用如下方式定义a == b
bool operator==(const double& a, const double& b) const
{
return fabs(a - b) < eps; // eps 代表精度差,一般设置为1e-6, 1e-8等
}
而set
去重的方式为 (a < b == false) && (a > b == false)
即 a 不小于 b 且 a 不大于 b
因此重定义比较函数即可
为什么不需要排序,但不用unordered_set
?
unordered_set
去重的原理和set
不同
- 计算元素hash值
- 检测相同hash值元素是否相等
也就是说,需要重定义hash
和operator==
,何必为了这点运行时间的提升浪费自己宝贵的竞赛/刷题时间
虽然看上去也不复杂就是了
以下代码源自Bing AI,未经验证
struct FloatEqual
{
bool operator() (const double x, const double y) const
{
return std::fabs(x - y) < 0.00001; // 误差范围设为0.00001
}
}
struct FloatHash
{
size_t operator() (const double x) const
{
return std::hash<int>()(static_cast<int>(x * 100000)); // 将double乘以100000转换为int
}
};
std::unordered_set<double, FloatHash, FloatEqual> mySet;
AC code 933ms
#include <bits/stdc++.h>
#define endl '\n'
#define x first
#define y second
using namespace std;
using PII = pair<int, int>;
using PDD = pair<double, double>;
const int MAX_N = 1e3 + 5, eps = 1e-8;
struct cmp
{
bool operator() (const PDD& a, const PDD& b) const
{
if (fabs(a.x - b.x) > eps) return a.x < b.x;
return a.x + eps < b.x;
}
};
int N;
set<PII> lines;
int work(int A, int B)
{
set<PDD, cmp> points;
for (auto line : lines)
{
int k = line.x, b = line.y;
if (A == k) continue;
double x = (double)(B - b) / (k - A);
double y = A * x + B;
points.emplace(make_pair(x, y));
}
return points.size() + 1;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> N;
int A, B, res = 1;
for (int i = 0; i < N; ++ i)
{
cin >> A >> B;
if (lines.count({A, B})) continue;
res += work(A, B);
lines.emplace(make_pair(A, B));
}
cout << res << endl;
return 0;
}