蓝桥杯2021年省赛JAVA B组第三题

题目

在平面直角坐标系中,两点可以确定一条直线。如果有多点在一条直线上,那么这些点中任意两点确定的直线是同一条。
给定平面上 2×3 个整点{(x,y)losx <20y<3,xeZ,yeZ,即横坐标是0到1(包含0和1)之间的整数、纵坐标是0到 2(包含0 和 2)之间的整数的点。这些点一共确定了11条不同的直线。
给定平面上 20×21 个整点{(x,)o x < 20,0y< 21,xZ,yez,即横坐标是0到19 (包含0和19)之间的整数、纵坐标是0到20(包含0和 20)之间的整数的点。请问这些点一共确定了多少条不同的直线。

正确答案

40257

思路

这个由于是填空题,数据量也不算很恐怖,可以考虑一下暴力去遍历,用四层for循环去循环每两个点,算出来表达式,进行化简和塞入一个链表,最后把链表的size得出再加上特殊的水平线即可;

我在做题的时候碰到了很多问题:

1.直线表达式的选择

一般来说最先想到的一定是y=k⋅x+b,但是一旦出现除法就会出现精度问题(其实我也是看题解才知道的),如果选用一个不用除的,用几个整数就可以表示的话就很奈斯,于是一般式

这样可以完美的避开除法,最后ABC全部为整数,精度问题就可以完全避免

2.直线重复问题

这个问题有很多部分,

一种是2 4 4和1 2 2其实是一样的直线

还有一个是1 1 1和-1 -1 -1也其实是一样的直线

所以需要一个check方法

选出三个里面的最大值

一直循环,直到有一个i是三个数的公因数,同时除以i,以解决第一种情况,

最后将A统一弄成正的,可以避免第二种情况

    public static int[] move(int a, int b, int c) {
        int max = Math.max(a, b);
        max = Math.max(max, c);
        for (int i = 1; i <= max; i++) {
            if (a % i == 0 && b % i == 0 && c % i == 0) {
                a = a / i;
                b = b / i;
                c = c / i;
                i = 1;//i必须归1,不然会出现错误
                max = Math.max(a, b);//可以没有
                max = Math.max(max, c);//可以没有
            }
        }
        if (a<0){
            a=-a;
            b=-b;
            c=-c;
        }
        return new int[]{a, b, c};
    }

还有一种重复的情况:

在循环中,出现(0,0)(0,0)去计算ABC,所以进入时要x1 != x2 && y1 != y2,但是这就会导致一个问题,水平和垂直的线已经被排除在外了,需要去单独补充。

3.检查是否之前出现过

由于我们不需要去考虑优化,所以可以直接用一个大数组去承接,但是数组的扩容不是很好写,所以我们简单写一个String的链表

    public static class ListNode {
        String val;
        ListNode next;

        ListNode() {
        }

        ListNode(String val) {
            this.val = val;
        }
        
    }

如何去判断之前有没有出现过,把三位int的数整合到一个String,用String的equal方法判断

    public static boolean check(String str, ListNode head) {
        while (head != null) {
            if (str.equals(head.val)) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

记录数量

定义一个size,在查重之后加入链表时,size++,最后

上述方法无法测到的线条

水平和竖直的直线是无法记录的,要在最后加上。水平和竖直一共有41条。

完整代码

 public static class ListNode {
        String val;
        ListNode next;

        ListNode() {
        }

        ListNode(String val) {
            this.val = val;
        }

    }

    public static int[] move(int a, int b, int c) {
        int max = Math.max(a, b);
        max = Math.max(max, c);
        for (int i = 1; i <= max; i++) {
            if (a % i == 0 && b % i == 0 && c % i == 0) {
                a = a / i;
                b = b / i;
                c = c / i;
                i = 1;//i必须归1,不然会出现错误
                max = Math.max(a, b);//可以没有
                max = Math.max(max, c);//可以没有
            }
        }
        if (a < 0) {
            a = -a;
            b = -b;
            c = -c;
        }
        return new int[]{a, b, c};
    }


    public static void main(String[] args) {
        ListNode num = new ListNode();
        ListNode head = num;
        int size = 0;
        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 && y1 != y2) {//排除重合的点
                            System.out.println("x1,y1: (" + x1 + " ," + y1 + ")  x2,y2:( " + x2 + " " + y2 + ")");//最后有这句话,知道一下进度
                            int A = y1 - y2;
                            int B = x2 - x1;
                            int C = x1 * y2 - x2 * y1;
                            int[] ABC = move(A, B, C);
                            String abc = ABC[0] + "+" + ABC[1] + "+" + ABC[2];
                            if (check(abc, head)) {
                                num.next = new ListNode(abc);
                                size++;
                                System.out.println(abc);
                                //System.out.println("----------" + size);
                                num = num.next;//链表跳下一个
                            }

                        }
                    }
                }
            }
        }
        System.out.println(size + 41);//41必须加上
    }

    public static boolean check(String str, ListNode head) {
        while (head != null) {
            if (str.equals(head.val)) {
                return false;
            }
            head = head.next;
        }
        return true;
    }
版权声明:除特殊说明,博客文章均为栋dong原创,依据CC BY-SA 4.0许可证进行授权,转载请附上出处链接及本声明。
如有需要,请在留言板留言,或者添加我的QQ或者微信
我只是一个学生,如有错误或者侵权,请联系我,谢!
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
春节
快乐