直线【第十二届蓝桥杯研究生组（CC++）】

分析： 题目描述有20*21的整点，所以先把每个点存起来，或者直接遍历也行，然后对每两个点计算斜率和截距，对于没有斜率的竖直的20条线不计算，这里我是用pair<int, int>存的坐标点，pair<double, double>存的k, b，最后计算存的k,b对的个数，并加上20。 下一步想法就是去重，这里有个重要的知识点，就是double是有精读误差的，两个数可能是一样的，但是由于计算时精读误差导致不同。 最初我的想法是用map存，这样就可以自动去重，但是因为精度问题导致结果错了。 为了解决精读问题，要用两个数相减，绝对值误差小于 1 0 − 8 10^{-8} 10−8就是一样的数。因此，先对存储的k,b对排序，然后进行去重。

首先看下错误的：

#include<iostream>
#include<set>


using namespace std;
typedef pair<int, int> PIIi;
typedef pair<double, double> PIId;
PIIi a[500];
set<PIId> d;
int main()
{
          
   
	int n = 0;
	for(int i = 0; i < 20; i++)
	{
          
   
		for(int j = 0; j < 21;j++)
		{
          
   
			a[n++] = {
          
   i, j};
		}
	}

	for(int i = 0; i < n; i ++)
	{
          
   
		for(int j = 0; j < n; j ++)
		{
          
   
			if(a[i].first != a[j].first)
			{
          
   
				double k = (double)(a[j].second - a[i].second) / (a[j].first - a[i].first);
				double b = a[i].second - k * a[i].first;

				d.insert({
          
   k, b});

			}
		}
	}
	cout << d.size()+20;
	return 0;
}

最后是正确的

#include<iostream>
#include<set>
#include<algorithm>

using namespace std;
typedef pair<int, int> PIIi;
typedef pair<double, double> PIId;
PIIi a[500];
const int N = 200000;
PIId d[N];

int main()
{
          
   
	int n = 0;
	for(int i = 0; i < 20; i++)
	{
          
   
		for(int j = 0; j < 21;j++)
		{
          
   
			a[n++] = {
          
   i, j};
		}
	}
	int num = 0;
	for(int i = 0; i < n; i ++)
	{
          
   
		for(int j = 0; j < n; j ++)
		{
          
   
			if(a[i].first != a[j].first)
			{
          
   
				double k = (double)(a[j].second - a[i].second) / (a[j].first - a[i].first);
				double b = a[i].second - k * a[i].first;

				d[num++] = {
          
   k,b};

			}
		}
	}
	sort(d, d+num);
	int res = 1;
	for(int i = 1; i < num; i++)
	{
          
   
		if(fabs(d[i].second - d[i-1].second) > 1e-8 || fabs(d[i].first - d[i-1].first) > 1e-8) res++;
	}
	cout <<res+20;
	return 0;
}

另附上用结构体的写法

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 200000;

int n;
struct Line
{
          
   
    double k, b;
    bool operator< (const Line& t) const
    {
          
   
        if (k != t.k) return k < t.k;
        return b < t.b;
    }
}l[N];

int main()
{
          
   
    for (int x1 = 0; x1 < 20; x1 ++ )
        for (int y1 = 0; y1 < 21; y1 ++ )
            for (int x2 = 0; x2 < 20; x2 ++ )
                for (int y2 = 0; y2 < 21; y2 ++ )
                    if (x1 != x2)
                    {
          
   
                        double k = (double)(y2 - y1) / (x2 - x1);
                        double b = y1 - k * x1;
                        l[n ++ ] = {
          
   k, b};
                    }

    sort(l, l + n);
    int res = 1;
    for (int i = 1; i < n; i ++ )
        if (fabs(l[i].k - l[i - 1].k) > 1e-8 || fabs(l[i].b - l[i - 1].b) > 1e-8)
            res ++ ;
    cout << res + 20 << endl;

    return 0;
}