直线—省赛java

这道题要比后边几道有难度
尤其是，在算KB的时候，自己一定要带入具体的例子验证一下

用到了去重，这个用set就很好解决，但是这个KB真不好想

import java.util.List;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

public class C_直线 {
    static Set ans = new HashSet<>();
    //求最大公约数
    public static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static void getKB(int a, int b) {
    	//求出坐标
        int x1 = a / 100, x2 = b / 100;
        int y1 = a % 100, y2 = b % 100;

        // 计算 k 的最简分数
        int up = y1 - y2, down = x1 - x2;
        int div_k = gcd(up, down);//（最大公约数）
        //用纵坐标之差/gcd()算出分数形式的分子，同理用横坐标之差/gcd()算出分数形式的分母
        String K = (up / div_k) + " " + (down / div_k);//用字符串形式表示分数形式的K（斜率）

        //k 不存在时，即 down = 0 的情况，就是两个点的横坐标相等的时候，为一条竖线
        // 此时方程为 x = x1 or x2，都可，因为x1 == x2;
        if (down == 0) {
            ans.add("x = " + x1);
            return;
        }

        // 代入点 (x1, y1) 来计算 kx 和 y 的分数
        // 因为分母都是 down，所以只求分子就好
        //为求得B而铺垫
        int up_kx = up * x1, up_y = y1 * down;

        // 计算 b = y - kx 的最简分数
        int up_b = up_y - up_kx;
        int div_b = gcd(up_b, down);
        String B = (up_b / div_b) + " " + (down / div_b);

        // 加入答案
        ans.add(K + "  " + B);//本身包括去重了
    }
    public static void main(String[] args) {
        Set set = new HashSet<>();

        int x = 19, y = 20;
        for (int i = 0; i <= x; i++) {
            for (int j = 0; j <= y; j++) { 
            	//把每个点，的坐标当成一个数，存在set里边，x坐标i*100，y坐标就是j本身
                set.add(i * 100 + j);
            }
        }

        List arr = new ArrayList<>(set);
        int len = arr.size();
        for (int i = 0; i < len; i++) {
            int a = arr.get(i);
            for (int j = i + 1; j < len; j++) {
                int b = arr.get(j);
                //a是一个点，b是相邻的第一个点，第二个点.......到最后一个点
                getKB(a, b);
            }
        }
        System.out.println("ans = " + ans.size());
    }
}

答案：40257

友情链接：12届最全蓝桥javaB组详解