Doratmon 2022-02-23 22:54 采纳率: 100%
浏览 81
已结题

第十一届蓝桥杯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;

解决方案

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

平面切分,题目

img

img

  • 写回答

2条回答 默认 最新

  • _GX_ 2022-02-24 01:01
    关注

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

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 4月20日
  • 已采纳回答 4月12日
  • 修改了问题 2月27日
  • 创建了问题 2月23日

悬赏问题

  • ¥50 树莓派安卓APK系统签名
  • ¥15 maple软件,用solve求反函数出现rootof,怎么办?
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗