题号：NC18951【两条斜线】Java版

柔情只为你懂 2023-10-13 12:18 4阅读 0赞

### 题目描述 ###

平面上有n个点,现在你需要建造两条路，一条是斜率为1,  
另一条斜率为-1  
你的任务是让这两条路经过尽可能多的点  
求最多经过几个点

### 输入描述: ###

第一行输入一个整数N表示点的个数
    第二行输入N个数表示X坐标
    第三行输入N个数表示Y坐标
    1<=N<=1000 ,0<=x[i],y[i]<=999

### 输出描述: ###

输出一个整数

示例1

### 输入 ###

>     4
>     1 4 4 5
>     3 0 2 3

### 输出 ###

>     4

### 说明 ###

>     (1,3) (4,0) (4,2) (5,3)四个点都可以被经过

### 题解 ###

设斜率为1的直线为：y = x + b1，可得 y- x = b1;

设斜率为-1的直线为：y = -x + b2, 可得y + x = b2;

所有的点都会在这样的两条直线上，不同的是b1和b2

那么，计算出所有点的b1值，如果不同点的b1值相同，说明它们在一条直线上。我们将b1值作为键，在y = x + b1上的点的个数作为值。用map集合存储这样的键值对。

同理，我们也能得到斜率为-1的直线的键值对。

最后，计算出经过的最多的点  
计算公式是：斜率为1直线上的点 + 斜率为-1直线上的点 - 两条线上的交点

需要两层循环进行遍历，找出最大值。

刚开始错误的想法是：斜率为1直线上最多的点 + 斜率为-1直线上最多的点 - 两条线上的交点

这样的话并不能保证求得的结果是最大值。

public class Main{
        public static void main(String[] args){
            //1. 处理输入的数据
            int b1 = 0;
            int b2 = 0;
            Scanner sc =new Scanner(System.in);
            int num = sc.nextInt();
            //2. 特判 
            if(num == 1 || num == 2){
                System.out.println(num);
                return;
            }
            HashMap<Integer,Integer> mapB1 = new HashMap<>();
            HashMap<Integer,Integer> mapB2 = new HashMap<>();
            int[] x = new int[num];
            int[] y = new int[num];
            for(int i = 0; i < num;i++){
                x[i] = sc.nextInt();
            }
            //3 统计在斜率1和-1上不同直线上的点的个数
            for(int i = 0; i < num; i++){
                y[i] = sc.nextInt();
                b1 = y[i] - x[i];
                b2 = y[i] + x[i];
                //斜率为1的直线
                if(mapB1.containsKey(b1)){
                    mapB1.put(b1, mapB1.get(b1) + 1);
                }else{
                    mapB1.put(b1, 1);
                }
                //斜率为-1的直线
                if(mapB2.containsKey(b2)){
                    mapB2.put(b2, mapB2.get(b2) + 1);
                }else{
                    mapB2.put(b2, 1);
                }
            }
            //4. 计算出经过的最多的点
            //计算公式是：斜率为1直线上的点 + 斜率为-1直线上的点 - 两条线上的交点
            //错误的想法是：斜率为1直线上最多的点 + 斜率为-1直线上最多的点 - 两条线上的交点
            int max_value = 0;
            for(Integer k1:mapB1.keySet()){
                Integer v1 = mapB1.get(k1);
                for(Integer k2:mapB2.keySet()){
                    Integer v2 = mapB2.get(k2);
                    double x_commen = (k2 - k1)*0.5;
                    double y_commen = x_commen + k1;
                    int rest = 0;
                    //计算交点的个数 如果输入中没有重复点，那么只能是1个交点
                    //这里是为了防止有重复点，所以计算了交点的个数
                    for (int i = 0; i < x.length; i++) {
                        if (x[i] == x_commen && y[i] == y_commen) {
                            rest++;
                        }
                    }
                    if(max_value < v1 + v2 - rest){
                        max_value = v1 + v2 - rest;
                    }
                }
            }
            System.out.println(max_value);
        }
    }

### 结果 ###

![c060d7c2489b48eeadd01d7ef2ea73bd.png][]

### 其他解法 ###

import java.util.Scanner;
    public class Main{
        static int N = 2010;
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int x[] = new int[N];
            int y[] = new int[N];
            int k1[] = new int[N];
            int k2[] = new int[N];
            int k3[][] = new int[N][N];
            for(int i = 1;i <= n;i++) x[i] = sc.nextInt();
            for(int i = 1;i <= n;i++) y[i] = sc.nextInt();
            for(int i = 1;i <= n;i++){
                k1[y[i] - x[i] + 1000]++;//1  b1 = y - x
                k2[y[i] + x[i]]++;//-1        b2 = y + x
                k3[y[i] - x[i] + 1000][y[i] + x[i]]++;//    既在b1上又在b2上
            }
            int res = 0;
            for(int i = 0;i < N;i++){
                for(int j = 0;j < N;j++){
                    res = Math.max(res, k1[i] + k2[j] - k3[i][j]);
                }
            }
            System.out.println(res);
        }
    }

链接：[登录—专业IT笔试面试备考平台\_牛客网][IT]

[c060d7c2489b48eeadd01d7ef2ea73bd.png]: https://img-blog.csdnimg.cn/c060d7c2489b48eeadd01d7ef2ea73bd.png
[IT]: https://ac.nowcoder.com/acm/problem/18951