小易是这个游戏的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),表示每只怪物所在坐标的纵坐标,以空格分割。
输出一个整数表示小易最多能消灭多少只怪物。
5 0 -1 1 1 -1 0 -1 -1 1 1
5
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); } }