求解答
这两段理论上来说应该一样的代码,却只有一个能通过所有测试用例
- 两段代码的不同点在求直线交点那里
设两条直线方程为
y=ax+b
y=Ax+B
那么x = (B-b) / (a-A)
计算出x后理论上随便带入任意一个方程都能求出y
然而这里只有带入a,b的那一段代码能通过所有测试用例
- 不同的地方
double x = 1.0 * (B - b) / (a - A);
double y = x * a + b;
double x = 1.0 * (B - b) / (a - A);
double y = x * A + B;
解决方案
在使用set保存pair浮点数坐标时,不能用first的值去计算second的值,并且在计算时只能有一个除法,否者会出现精度偏差使两个相同的pair<double,double>被set保存
- 修改后的代码
double x = 1.0 * (B - b) / (a - A);
double y = 1.0 * (B * a - A * b) / (a - A);
上代码
- 能AC的
#include <bits/stdc++.h>
using namespace std;
int n, ans = 1;
set<pair<int, int>> line;
int calc(int a, int b)
{
set<pair<double, double>> node;
for (auto i : line)
{
int A = i.first, B = i.second;
if (A == a)
continue;
double x = 1.0 * (B - b) / (a - A);
double y = x * a + b;
node.insert(make_pair(x, y));
}
return node.size() + 1;
}
signed main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
int a, b;
cin >> a >> b;
if (line.find(make_pair(a, b)) != line.end())
continue;
ans += calc(a, b);
line.insert(make_pair(a, b));
}
cout << ans << '\n';
return 0;
}
- 不能AC的
#include <bits/stdc++.h>
using namespace std;
int n, ans = 1;
set<pair<int, int>> line;
int calc(int a, int b)
{
set<pair<double, double>> node;
for (auto i : line)
{
int A = i.first, B = i.second;
if (A == a)
continue;
double x = 1.0 * (B - b) / (a - A);
double y = x * A + B;
node.insert(make_pair(x, y));
}
return node.size() + 1;
}
signed main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
int a, b;
cin >> a >> b;
if (line.find(make_pair(a, b)) != line.end())
continue;
ans += calc(a, b);
line.insert(make_pair(a, b));
}
cout << ans << '\n';
return 0;
}