射击游戏_网易笔试题

小易正在玩一款新出的射击游戏,这个射击游戏在一个二维平面进行,小易在坐标原点(0,0),平面上有n只怪物,每个怪物有所在的坐标(x[i], y[i])。小易进行一次射击会把x轴和y轴上(包含坐标原点)的怪物一次性消灭。
小易是这个游戏的VIP玩家,他拥有两项特权操作:
1、让平面内的所有怪物同时向任意同一方向移动任意同一距离
2、让平面内的所有怪物同时对于小易(0,0)旋转任意同一角度
小易要进行一次射击。小易在进行射击前,可以使用这两项特权操作任意次。

小易想知道在他射击的时候最多可以同时消灭多少只怪物,请你帮帮小易。

如样例所示:

所有点对于坐标原点(0,0)顺时针或者逆时针旋转45°,可以让所有点都在坐标轴上,所以5个怪物都可以消灭。

输入包括三行。第一行中有一个正整数n(1 ≤ n ≤ 50),表示平面内的怪物数量。第二行包括n个整数x[i](-1,000,000 ≤ x[i] ≤ 1,000,000),表示每只怪物所在坐标的横坐标,以空格分割。第二行包括n个整数y[i](-1,000,000 ≤ y[i] ≤ 1,000,000),表示每只怪物所在坐标的纵坐标,以空格分割。

数学

这个题很有意思，对于小易的两种特权操作，无论是所有的怪物都往一个方向移动一步，还是所有怪物都以原点为中心旋转一个角度，所有怪物的相对于位置都是不变的。所以原始位置就已经决定了最终最多可以消灭多少个怪物。

我们可以从n个坐标中选择3个，过这三个点做两条垂线（前两个点x和y确定一条直线L1，第三个点z做一条过L1的垂线L2），L1和L2能通过的最多点数，就是最多能同时消灭的怪物数。

判断某个点p是否在这两条垂线上，可以用数学的方法，构建向量

$v_1=[y[0]-x[0],y[1]-x[1]]$

$v_2=[z[0]-p[0],z[1]-p[1]]$

$v_3=[p[0]-x[0],p[1]-x[1]]$

如果 $v_1$ 和 $v_2$ 内积为0，则说明p点在垂线上；如果 $v_1$ 和 $v_3$ 共线，说明p点在方向向量 $v_1$ 确定的直线上。

若 $v_1$ 和 $v_3$ 共线，则有： $\frac{p[0]-x[0]}{y[0]-x[0]}=\frac{p[1]-x[1]}{y[1]-x[1]}$

为了避免讨论分母为0的情况，交叉相乘得到： $v_1[0]*v_3[1]=v_1[1]*v_3[0]$

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while((line = br.readLine()) != null){
            int n = Integer.parseInt(line);
            String[] strs = br.readLine().split(" ");
            int[] x = new int[n];
            for(int i = 0; i < n; i++){
                x[i] = Integer.parseInt(strs[i]);
            }
            strs = br.readLine().split(" ");
            int[] y = new int[n];
            for(int i = 0; i < n; i++){
                y[i] = Integer.parseInt(strs[i]);
            }
            System.out.println(solve(n, x, y));
        }
    }
    
    public static int solve(int n,int[] x,int[] y){
        if(n <= 2){
            return n;
        }
        int res = 0;
        for(int i = 0; i < n; i++){        // 确定第一个点
            for(int j = 0; j < n; j++){    // 确定第二个点
                if(i != j){
                    int[] v1 = {x[j] - x[i], y[j] - y[i]};
                    for(int k = 0; k < n; k++){    // 确定第三个点
                        int count = 0;
                        if(k != i && k != j){
                            for(int r = 0; r < n; r++){
                                int[] v2 = {x[r] - x[k], y[r] - y[k]};
                                int[] v3 = {x[r] - x[i], y[r] - y[i]};
                                if(v1[0]*v2[0] + v1[1]*v2[1] == 0 || v3[0]*v1[1] == v3[1]*v1[0]) {
                                    count++;
                                }
                            }
                        }
                        res = Math.max(res, count);
                    }
                }
            }
        }
        return res;
    }
}

射击游戏

输入描述:

输出描述:

输入

输出

数学

问题信息

热门推荐

通过挑战的用户

相关试题