小易是这个游戏的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.io.*; import java.util.*; public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String line; while((line = br.readLine()) != null){ int n = Integer.parseInt(line); String[] strs = br.readLine().split(" "); int[] x = new int[n]; for(int i = 0; i < n; i++){ x[i] = Integer.parseInt(strs[i]); } strs = br.readLine().split(" "); int[] y = new int[n]; for(int i = 0; i < n; i++){ y[i] = Integer.parseInt(strs[i]); } System.out.println(solve(n, x, y)); } } public static int solve(int n,int[] x,int[] y){ if(n <= 2){ return n; } int res = 0; for(int i = 0; i < n; i++){ // 确定第一个点 for(int j = 0; j < n; j++){ // 确定第二个点 if(i != j){ int[] v1 = {x[j] - x[i], y[j] - y[i]}; for(int k = 0; k < n; k++){ // 确定第三个点 int count = 0; if(k != i && k != j){ for(int r = 0; r < n; r++){ int[] v2 = {x[r] - x[k], y[r] - y[k]}; int[] v3 = {x[r] - x[i], y[r] - y[i]}; if(v1[0]*v2[0] + v1[1]*v2[1] == 0 || v3[0]*v1[1] == v3[1]*v1[0]) { count++; } } } res = Math.max(res, count); } } } } return res; } }