首页 > 试题广场 >

射击游戏

[编程题]射击游戏

热度指数：271 时间限制：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

重洋

import java.util.*;
public class Main {
     
    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];
        for(int i=0; i<n; i++)
            x[i] = sc.nextInt();
        for(int i=0; i<n; i++)
            y[i] = sc.nextInt();
        
        if(n<=3)
        {
            System.out.println(n);
            return;
        }
        
        int max=0;
        for(int i=0;i<n;i++)
            for(int j=i+1;j<n;j++)
                for(int k=0;k<n;k++)
                {
                	if(k==i || k==j)
                		continue;
                    int count=0;
                    //k=A，l=B，若l在k代表的Y轴上，则k=B时，仍在此Y轴上，总count不变，不计算l=A也可，反正不会更大； 
                    //若l不在k代表的Y轴上，则不关于Y轴计数，等到k=B时，l=A也就不在Y轴上，不关于Y轴计数，故不必向前考虑
                                        //for(int l=0;l<n;l++) 不影响结果
                                        for(int l=k+1;l<n;l++)
                    {
                    	if(l==i || l==j || l==k)
                    		continue;
                        if((y[i]-y[j])*(x[i]-x[l])==(y[i]-y[l])*(x[i]-x[j]))
                            count++;
                        else if((x[i]-x[j])*(x[k]-x[l])==-(y[k]-y[l])*(y[i]-y[j]))
                            count++;
                    }
                    max=max>count?max:count;
                }
        System.out.println(max+3);
    }
}

编辑于 2019-09-05 21:33:34 回复(0)