首页 > 试题广场 >

射击游戏

[编程题]射击游戏

热度指数：65 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小易正在玩一款新出的射击游戏,这个射击游戏在一个二维平面进行,小易在坐标原点(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),表示每只怪物所在坐标的纵坐标,以空格分割。

输出描述:

输出一个整数表示小易最多能消灭多少只怪物。

示例1

输入

5
0 -1 1 1 -1
0 -1 -1 1 1

输出

算法知识视频讲解

Java

sendren

思路：先选择3点，前两个点构造一条直线，后面一个点构造一条垂直于前一条直线的直线，然后枚举剩下的点是否在这两条线上。
涉及到的数学知识：
判断一个点是否在某直线上有两个点（x1，y1）（x2，y2），待判断的点（x3，y3），
如果（x3-x1）/（y3-y1）=（x2-x1）/（y2-y1），则共线

判断是否在垂线上：
运用的公理：两垂直线的斜率之积为-1
直线上有两个点（x1，y1）（x2，y2），垂线上点（x4，y4）待判断的点（x3，y3）。
（x2-x1）/（y2-y1）*（x3-x4）/（y3-y4）=-1，则该点在垂线上。
————————————————
public class ShotGame{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int n=sc.nextInt();
            int[] x=new int[n];
            int[] y=new int[n];
            for(int i=0;i<n;i++){
                x[i]=sc.nextInt();
            }
            for(int i=0;i<n;i++){
                y[i]=sc.nextInt();
            }
            int res=solve(n,x,y);
            System.out.println(res);
        }
    }
    public static int solve(int n,int[] x,int[] y){
        int res = 1;
        if (n <= 2)return n;
        for (int i=0; i<n; i++) { //first point
            for (int j=0; j<n; j++) { //second point
                if (i != j){
                    int dx1 = x[j] - x[i];
                    int dy1 = y[j] - y[i];
                    for (int k=0; k<n; k++) { //third point
                        int count = 0;
                        if (k != i && k != j){
                            for (int r=0; r<n; r++) {
                                int dx2 = x[r] - x[i];
                                int dy2 = y[r] - y[i];
                                if (dy1*dx2 == dx1*dy2) {//判断当前点是否和选定的前两个点在同一条直线上
                                    count++;
                                }else{
                                    dx2 = x[r] - x[k];
                                    dy2 = y[r] - y[k];
                                    if (dy1*dy2 == -dx1*dx2) {//判断当前点是否在选定的第三个点和前两个点形成垂直的线上
                                        count++;
                                    }
                                }
                            }
                        }
                        res = Math.max(res, count);
                    }
                }
            }
        }
        return res;
    }

编辑于 2021-07-21 14:41:12 回复(0)