[数据结构与算法]「蓝桥杯」直线（Java）

第十二届蓝桥杯省赛javaB组第3题

这道题比赛的话我大概率做不出来。

涉及到直线问题我们需要考虑斜率和截距：

直线：$y=kx+b$，$k$ 是斜率，$b$ 是截距，我们可以用一个类来存斜率和截距。

第一步：在给定范围内，任意两个点之间构成一条直线

第二步：求出非重边的条数

需要注意的点：

① 因为斜率可能是小数，所以要用浮点型数据进行比较，对于 $doublea,b$ ，如果 $|a?b|\le 1e^{?8}$ 则 $a,b$ 相等。

② 非重边：斜率或者截距不相等

③ 因为垂直于x轴的直线有20条，斜率和截距都相等，因此最后统计非重边条数的时候要+20

import java.util.Arrays;

public class Main {

    static final int N = 200010;
    static Line[] line = new Line[N];
    static int n;

    public static void main(String[] args) {
        for (int x1 = 0; x1 <= 19; x1++) {
            for (int y1 = 0; y1 <= 20; y1++) {
                for (int x2 = 0; x2 <= 19; x2++) {
                    for (int y2 = 0; y2 <= 20; y2++) {
                        if (x1 != x2) {
                            double k = (double) (y2 - y1) / (x2 - x1);
                            double b = k * x1 - y1;
                            line[n++] = new Line(k, b);
                        }
                    }
                }
            }
        }

        Arrays.sort(line, 0, n);

        int res = 1;
        for (int i = 1; i < n; i++) {
            // 求斜率或者截距不等
            if (Math.abs(line[i].k - line[i - 1].k) > 1e-8 || Math.abs(line[i].b - line[i - 1].b) > 1e-8) {
                res++;
            }
        }

        System.out.println(res + 20); // 最后要加上20
    }

    static class Line implements Comparable<Line> {
        double k; // 斜率
        double b; // 截距

        public Line(double k, double b) {
            this.k = k;
            this.b = b;
        }

        @Override
        public int compareTo(Line o) {
            if (this.k > o.k) return 1;
            if (this.k == o.k) {
                if (this.b > o.b) return 1;
                return -1;
            }
            return -1;
        }
    }
}