题目

在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上， 那么这些点中任意两点确定的直线是同一条。

给定平面上 2 × 3 个整点{(x, y)|0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z}(x,y)∣0≤x<2,0≤y<3,x∈Z,y∈Z​，即横坐标 是 00 到 11 (包含 0 和 1) 之间的整数、纵坐标是 0 到 2 (包含 0 和 2) 之间的整数 的点。这些点一共确定了 11 条不同的直线。

给定平面上 20 × 2120×21 个整点 {(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z}(x,y)∣0≤x<20,0≤y<21,x∈Z,y∈Z，即横 坐标是 00 到 1919 (包含 00 和 1919) 之间的整数、纵坐标是 00 到 2020 (包含 00 和 2020​) 之 间的整数的点。

请问这些点一共确定了多少条不同的直线。

思路

1.枚举任意两点的坐标，算出所有的斜率和截距（截距不存在的类似x=1的特判，最后加上20）
2.然后按照斜率和截距排序（斜率如果相同则按截距）如果相邻两个的斜率或者截距的绝对值>1e-8,则说明存在一条不同的直线。

c++代码

#include<iostream>
#include<algorithm>
#include<vector>
#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)(y1-y2)/(x1-x2);
                        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++;//注意double有误差
        //不能写为l[i].k==l[i-1].k
    }
    cout<<res+20<<endl;
    return 0;
}