直线–2021蓝桥杯Java组

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

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

给定平面上 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​) 之 间的整数的点。

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

运行限制

最大运行时间：1s
最大运行内存: 128M

分析：

• 条件定义：
  给定点，求这些点之间不同的直线条数
  不同直线定义：在坐标轴中不会重合成一条
• 构建数据结构表示不同的点：
  根据给定数据我们得知x 与 y 都不会超过两位，则我们可以用一个整数表示一个点
  即：int point = x * 100 + y;
• 构建数据结构表示直线：
  在坐标轴中确定一条直线有点斜式、斜截式、两点式、截距式，这里我们使用斜截式y = kx + b来表示一条直线，实际上就是k与b确定一条直线，则k = y1- y2 / x1 - x2 , b = y1 - kx1
  注意 :我们如果直接这样计算k与b的值来确定一条直线在实际上是不行的（理论可以），因为java 运算时的精度不够导致计算k与b的时候得到大于正确结果的直线数量（使用C/C++的貌似能直接AC）所以采用最简分数（两个整形数据）表示，而最终的一条直线就是由两个分数即四个整形确定,当然对于没有斜率的直线我们直接用横坐标表示

AC代码：

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        List<Integer> points = new ArrayList<>();
        Set<String> ans = new HashSet<>();
        for(int i = 0; i < 20; i ++){
            for (int j = 0; j < 21; j++) {
                points.add(i * 100 + j); //存xy
            }
        }
        int size = points.size();
        for (int i = 0; i < size; i++) {
            int node1 = points.get(i);
            int x1 = node1 / 100, y1 = node1 % 100;
            for (int j = i + 1; j < size; j++) {
                int node2 = points.get(j);
                int x2 = node2 / 100, y2 = node2 % 100;
                int up = y1 - y2, down = x1 - x2;
                if(down == 0){
                    ans.add("x = " + x1);
                    continue;
                }
                int c1 = gcd(up, down);
                String K = up / c1 + " " + down / c1;
                int Up = y1 * down - x1 * up;
                int c2 = gcd(Up, down);
                String B = Up/c2 + " " + down / c2;
                ans.add(K + " " + B);
            }
        }
        System.out.println(ans.size());
    }
    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}