2021省赛题：直线

题目描述：
在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上，那么这些点中任意两点确定的直线是同一条。
给定平面上2 ✖ 3个整点{(x, y)|0 <= x < 2, 0 <= y < 3, x, y ∈ Z}，即横坐标是0到1之间的整数、纵坐标是0到2之间的整数。这些点一共确定了11条不同的直线。
现在将范围改成0 <= x < 20，0 <= y < 21，求一共确定多少条直线。

思路

两点确定一条直线，如果只是单纯的用两点判断同一条直线的话显然是不可能的（至少我写不出来）。但是确定一条直线还有一个更好的方法就是求直线的方程式，只要求出两点所在的直线的斜率和截距，即可确定一条直线。

步骤

1、遍历两点，分别求出两点对应的斜率和截距（如果是同一个点则跳过）
2、将斜率和截距放入容器中
3、输出容器的大小，即直线的数量

代码

  1. #include<iostream>
  2. #include<unordered_map>
  3. #include<utility>
  4. #include<set>
  5. using namespace std;
  7. int main()
  8. {
  9.     int xLen = 20;
  10.     int yLen = 21;
  12.     set<pair<double, double>> ret;
  14.     for(int x1 = 0; x1 < xLen; x1++)
  15.     {
  16.         for(int y1 = 0; y1 < yLen; y1++)
  17.         {
  18.             for(int x2 = 0; x2 < xLen; x2++)
  19.             {
  20.                 for(int y2 = 0; y2 < yLen; y2++)
  21.                 {
  22.                     if(x1 == x2 && y1 == y2)
  23.                     {
  24.                         continue;
  25.                     } 
  26.                     double k = (double)(x2 - x1) / (y2 - y1);
  27.                     double b=(y2*(x2-x1)-(y2-y1)*x2)*1.0/(x2-x1);
  28.                     //cout << "not end" << endl;
  29.                     pair<double, double> element(k, b);
  30.                     ret.insert(element);
  31.                 }
  32.             }
  33.         }
  34.     }
  36.     cout << ret.size() + 21 + 20;
  38.     return 0;
  39. }

不足之处

1、去重的那一步我本来是想着用map容器，然后判断是否有重复值，但是看了下答案有个更好的方法，就是用set容器，因为set有个特点就是没有重复值，这样就节省了去重的操作。
2、在求截距的时候，我第一次是直接用b = y - k b这个公式，但是这样的话会出现精度误差，导致结果远大于正确值，因此这里用b=(y2(x2-x1)-(y2-y1)*x2)/(x2-x1)，这样可以很好的规避精度问题。

反思

1、对set容器的操作及特性不熟悉
2、没有考虑到精度的问题
这样即使有了正确的思路也没办法写出正确答案。