第十一届蓝桥杯C/C++ 试题I 平面切分,遇到一个很奇怪的问题

求解答

这两段理论上来说应该一样的代码,却只有一个能通过所有测试用例

• 两段代码的不同点在求直线交点那里

设两条直线方程为

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;

• dotcpp题目链接
  https://www.dotcpp.com/oj/problem2589.html

解决方案

在使用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;
}

平面切分,题目

这可能是由于浮点计算误差导致。你求交点时，不要作除法运算，而采用最简分数形式表示（即用两个整数分别表示分子分母）。

我看代码是几乎一样的，按我觉得的话应该是两个都不行，这里好像没有考虑平行线的问题。