(笔试)射击游戏

题目：

小易正在玩一款新出的射击游戏,这个射击游戏在一个二维平面进行,小易在坐标原点(0,0),平面上有n只怪物,每个怪物有所在的坐标(x[i], y[i])。小易进行一次射击会把x轴和y轴上(包含坐标原点)的怪物一次性消灭。

小易是这个游戏的VIP玩家,他拥有两项特权操作:

1、让平面内的所有怪物同时向任意同一方向移动任意同一距离

2、让平面内的所有怪物同时对于小易(0,0)旋转任意同一角度

小易要进行一次射击。小易在进行射击前,可以使用这两项特权操作任意次。

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

输入描述：

链接：

输入包括三行。

第一行中有一个正整数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),表示每只怪物所在坐标的纵坐标,以空格分割。

输出描述：

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

示例：

输入：

5

0 -1 1 1 -1

0 -1 -1 1 1

输出：

5

错误做法： 这个题就是想让尽可能多的点处于X或者Y轴，刚开始想到的解决思路是先解决平移，找出横纵坐标数组中，最多出现的元素，再找出它的所有下标，将该它定义为0，对横纵数组进行对比，只要横坐标或者纵坐标中含有0，就视为该点为最多方案中的一点，找出所有点，记录它的数目；接着解决旋转，将每个点和原点连线的斜率装入一个数组，查出这个数组中斜率相差为-1或者斜率相等的，在记录他们的数目，遍历后找出最大的数目，再和之前旋转得到的数目作比较，输出最大数目。

错误点： 首先，旋转和平移分开计算就是错误的，存在某种点的结构，需要平移+旋转后能得到最多点的方案，而不是单独的平移或者旋转，其次，通过斜率存在除0错，而且若两个斜率相乘为-1后，无法保存当前信息，因为只是斜率，没有点的信息

正确思路：

与其说平移点，不如说拿出一个十字架一样的坐标轴，在点集中去移动，看那种情况落在坐标轴的最多；首先拿出三个不同且不共线的点A、B、C，AB做为一个坐标轴，再取一个不为A B C的三点一个点D，若AB//AD||CD⊥AB，则视为满足条件，则点方案数+1，这些是点的数目超过4个之后，需要额外考虑的就是点数目为3的时候，存在有可能能在平移后所有点都在坐标轴的，也有不能的，3个点的处理情况和4个及以上有不同，不同在于只要判断这3点斜率的绝对值相同，那么3点都能处于坐标轴，否则只能两点。

代码：

import java.util.Scanner;

public class Revolve {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int count = sc.nextInt();
		
		int[] row = new int[count];
		int[] col = new int[count];
		
		for(int i=0;i<count;i++) {
			int x = sc.nextInt();
			row[i] = x;
		}
		
		for(int j=0;j<count;j++) {
			int y = sc.nextInt();
			col[j] = y;
		}
		
		int maxnum = 0;
		if(count==2||count==1) 
			maxnum =count;
		if(count==3) {
			int row0 = Math.abs(row[0]);
			int row1 = Math.abs(row[1]);
			int row2 = Math.abs(row[2]);
			
			int col0 = Math.abs(col[0]);
			int col1 = Math.abs(col[1]);
			int col2 = Math.abs(col[2]);
			
			if(row0*col1==col0*row1&&row2*col1==col2*row1&&row2*col0==col2*row0) {
				maxnum = 3;
			}
			if(row[0]==row[1]||row[1]==row[2]||row[0]==row[2]||col[0]==col[1]||col[1]==col[2]||col[0]==col[2]) {
				maxnum = 3;
			}
			else {
				maxnum = 2;
			}
		}
		else{
			for(int i=0;i<row.length;i++) {
				int x1 = row[i];
				int y1 = col[i];
				for(int j=i+1;j<row.length;j++) {
					int x2 = row[j];
					int y2 = col[j];
					for(int k=0;k<row.length;k++) {
						if(k==i||k==j) {
							break;
						}
						int counts=3;
						
						int x3 = row[k];
						int y3 = col[k];	
						
						for(int o=0;o<row.length;o++) {
							if(o==i||o==j||o==k) {
								break;
							}
							
							int x4 = row[o];
							int y4 = col[o];
							
							int Xab = x2-x1;
							int Yab = y2-y1;
							
							int Xad = x4-x1;
							int Yad = y4-y1;
							
							int Xcd = x3-x4;
							int Ycd = y3-y4;
							
							if((Xab*Yad==Xad*Yab)||(Xab*Ycd+Xcd+Yab==0)) {
	  							counts++;
							}
							
							if (counts > maxnum)
								maxnum = counts;
						}
						
					}
				}
			}
		}
		System.out.println(maxnum);
		
	}
}

           

测试可行！