(筆試)射擊遊戲

題目：

小易正在玩一款新出的射擊遊戲,這個射擊遊戲在一個二維平面進行,小易在坐标原點(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);
		
	}
}

           

測試可行！