0_0_23318925_11495\Main.java:2: 错误: 解析时已到达文件结尾
public class Main{ static int x_center = -1; static int y_center = -1; /** Some Helper Utilities **/ static int distance(int x1, int y1, int x2, int y2) { return Math.abs(x1 - x2) + Math.abs(y1 - y2); } static int e_distance(int x1, int y1, int x2, int y2) { return (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2); } static int min(int []arr) { int min = arr[0]; for(int i = 1; i < arr.length; i++) if(min > arr[i]) min = arr[i]; return min; } static int max(int []arr) { int max = arr[0]; for(int i = 1; i < arr.length; i++) if(max < arr[i]) max = arr[i]; return max; } private static void solveLocateCenterNaive(int [] sites_x, int [] sites_y) { int min_max_so_far = -1; int min_max_so_far_x = -1; int min_max_so_far_y = -1; int min_x = min(sites_x); int max_x = max(sites_x); int min_y = min(sites_y); int max_y = max(sites_y); for(int x = min_x; x <= max_x; x++) { for(int y = min_y; y <= max_y; y++) { /* Compute the maximum distance to the points. */ int max_here = distance(sites_x[0], sites_y[0], x, y); for(int i = 1; i < sites_x.length; i++) { int d = distance(sites_x[i], sites_y[i], x, y); if(d > max_here) max_here = d; } // System.out.println(x + " " + y + " max_here = " + max_here); if( (min_max_so_far == -1) || (max_here < min_max_so_far)) { min_max_so_far = max_here; min_max_so_far_x = x; min_max_so_far_y = y; } if(max_here == min_max_so_far) { if(e_distance(x, y, 0, 0) < e_distance(min_max_so_far_x, min_max_so_far_y, 0, 0)) { min_max_so_far_x = x; min_max_so_far_y = y; } } } } x_center = min_max_so_far_x; y_center = min_max_so_far_y; } static void findClosestPointToCenter(int plus_min, int plus_max, int minus_min, int minus_max) { int min_so_far = -1; if(plus_min > plus_max) { findClosestPointToCenter(plus_max, plus_min, minus_min, minus_max); return; } if(minus_min > minus_max) { findClosestPointToCenter(plus_min, plus_max, minus_max, minus_min); return; } // System.out.println("Center located within " + plus_min + " " + plus_max + " " + minus_min + " " + minus_max); for(int i = plus_min; i <= plus_max; i++) { for(int j = minus_min; j <= minus_max; j++) { if((i + j) % 2 == 0) { int x = (i + j)/2; int y = (i - j)/2; if((min_so_far == -1) || (distance(x, y, 0, 0) < min_so_far)) { min_so_far = distance(x, y, 0, 0); x_center = x; y_center = y; } if(distance(x, y, 0, 0) == min_so_far) { if(e_distance(x, y, 0, 0) < e_distance(x_center, y_center, 0, 0)) { x_center = x; y_center = y; } } } } } } private static void solveLocateCenter(int [] sites_x, int [] sites_y) { /* ------------------- INSERT CODE HERE ---------------------*/ /* This is for minimizing the total sum of Manhatten distances. Arrays.sort(sites_x); x_center = sites_x[(int) (sites_x.length+1)/2]; Arrays.sort(sites_y); y_center = sites_y[(int) (sites_y.length+1)/2]; */ /* The following code is for minimizing the maximum distance to a site. * * Algorithm: Find a diamond that encloses all the points. * * This is however not unique, and we must find the one that **/ int max_x_plus_y = sites_x[0] + sites_y[0]; int min_x_plus_y = sites_x[0] + sites_y[0]; int max_x_minus_y = sites_x[0] - sites_y[0]; int min_x_minus_y = sites_x[0] - sites_y[0]; for(int i = 1; i < sites_x.length; i++) { if( (sites_x[i] + sites_y[i]) > max_x_plus_y) max_x_plus_y = sites_x[i] + sites_y[i]; if( (sites_x[i] + sites_y[i]) < min_x_plus_y) min_x_plus_y = sites_x[i] + sites_y[i]; if( (sites_x[i] - sites_y[i]) > max_x_minus_y) max_x_minus_y = sites_x[i] - sites_y[i]; if( (sites_x[i] - sites_y[i]) < min_x_minus_y) min_x_minus_y = sites_x[i] - sites_y[i]; } int sum_plus = max_x_plus_y + min_x_plus_y; int sum_minus = max_x_minus_y + min_x_minus_y; int diff_plus = max_x_plus_y - min_x_plus_y; int diff_minus = max_x_minus_y - min_x_minus_y; if(diff_plus > diff_minus) { /* Any point satisfying the following inequalities would work. * IF (diff_plus is even) THEN * x + y = sum_plus / 2 AND * x - y BETWEEN min_x_minus_y + diff_plus/2 AND max_x_minus_y - diff_plus/2 * ELSE * x + y BETWEEN (sum_plus - 1) / 2 AND (sum_plus + 1) / 2 * x - y BETWEEN min_x_minus_y + (diff_plus+1)/2 AND max_x_minus_y - (diff_plus+1)/2 */ if(diff_plus % 2 == 0) { findClosestPointToCenter(sum_plus/2, sum_plus/2, min_x_minus_y + diff_plus/2, max_x_minus_y - diff_plus/2); } else { findClosestPointToCenter((sum_plus-1)/2, (sum_plus+1)/2, min_x_minus_y + (diff_plus+1)/2, max_x_minus_y - (diff_plus+1)/2); } } else { /* Any point satisfying the following inequalities would work. * IF (diff_minus is even) THEN * x - y = sum_minus / 2 AND * x + y BETWEEN min_x_plus_y + diff_minus/2 AND max_x_plus_y - diff_minus/2 * ELSE * x - y BETWEEN (sum_minus - 1) / 2 AND (sum_minus + 1) / 2 * x + y BETWEEN min_x_plus_y + (diff_minus+1)/2 AND max_x_plus_y - (diff_minus+1)/2 */ if(diff_minus % 2 == 0) { findClosestPointToCenter(min_x_plus_y + diff_minus/2, max_x_plus_y - diff_minus/2, sum_minus/2, sum_minus/2); } else { findClosestPointToCenter(min_x_plus_y + (diff_minus+1)/2, max_x_plus_y - (diff_minus+1)/2, (sum_minus-1)/2, (sum_minus+1)/2); } /* -------------------- END OF INSERTION --------------------*/ } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int numCases = sc.nextInt(); for(int i = 0; i < numCases; i++) { int numberOfSites = sc.nextInt(); int [] sites_x = new int[numberOfSites]; int [] sites_y = new int[numberOfSites]; for(int j = 0; j < numberOfSites; j++) { sites_x[j] = sc.nextInt(); sites_y[j] = sc.nextInt(); } // solveLocateCenterNaive(sites_x, sites_y); // System.out.println("(NAIVE) Locate mining center at (" + x_center + ", " + y_center + ")."); x_center = -1; y_center = -1; solveLocateCenter(sites_x, sites_y); System.out.println("LOCATION " + x_center + " " + y_center); } } }
^
0_0_23318925_11495\Main.java:2: 错误: 解析时已到达文件结尾
public class Main{ static int x_center = -1; static int y_center = -1; /** Some Helper Utilities **/ static int distance(int x1, int y1, int x2, int y2) { return Math.abs(x1 - x2) + Math.abs(y1 - y2); } static int e_distance(int x1, int y1, int x2, int y2) { return (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2); } static int min(int []arr) { int min = arr[0]; for(int i = 1; i < arr.length; i++) if(min > arr[i]) min = arr[i]; return min; } static int max(int []arr) { int max = arr[0]; for(int i = 1; i < arr.length; i++) if(max < arr[i]) max = arr[i]; return max; } private static void solveLocateCenterNaive(int [] sites_x, int [] sites_y) { int min_max_so_far = -1; int min_max_so_far_x = -1; int min_max_so_far_y = -1; int min_x = min(sites_x); int max_x = max(sites_x); int min_y = min(sites_y); int max_y = max(sites_y); for(int x = min_x; x <= max_x; x++) { for(int y = min_y; y <= max_y; y++) { /* Compute the maximum distance to the points. */ int max_here = distance(sites_x[0], sites_y[0], x, y); for(int i = 1; i < sites_x.length; i++) { int d = distance(sites_x[i], sites_y[i], x, y); if(d > max_here) max_here = d; } // System.out.println(x + " " + y + " max_here = " + max_here); if( (min_max_so_far == -1) || (max_here < min_max_so_far)) { min_max_so_far = max_here; min_max_so_far_x = x; min_max_so_far_y = y; } if(max_here == min_max_so_far) { if(e_distance(x, y, 0, 0) < e_distance(min_max_so_far_x, min_max_so_far_y, 0, 0)) { min_max_so_far_x = x; min_max_so_far_y = y; } } } } x_center = min_max_so_far_x; y_center = min_max_so_far_y; } static void findClosestPointToCenter(int plus_min, int plus_max, int minus_min, int minus_max) { int min_so_far = -1; if(plus_min > plus_max) { findClosestPointToCenter(plus_max, plus_min, minus_min, minus_max); return; } if(minus_min > minus_max) { findClosestPointToCenter(plus_min, plus_max, minus_max, minus_min); return; } // System.out.println("Center located within " + plus_min + " " + plus_max + " " + minus_min + " " + minus_max); for(int i = plus_min; i <= plus_max; i++) { for(int j = minus_min; j <= minus_max; j++) { if((i + j) % 2 == 0) { int x = (i + j)/2; int y = (i - j)/2; if((min_so_far == -1) || (distance(x, y, 0, 0) < min_so_far)) { min_so_far = distance(x, y, 0, 0); x_center = x; y_center = y; } if(distance(x, y, 0, 0) == min_so_far) { if(e_distance(x, y, 0, 0) < e_distance(x_center, y_center, 0, 0)) { x_center = x; y_center = y; } } } } } } private static void solveLocateCenter(int [] sites_x, int [] sites_y) { /* ------------------- INSERT CODE HERE ---------------------*/ /* This is for minimizing the total sum of Manhatten distances. Arrays.sort(sites_x); x_center = sites_x[(int) (sites_x.length+1)/2]; Arrays.sort(sites_y); y_center = sites_y[(int) (sites_y.length+1)/2]; */ /* The following code is for minimizing the maximum distance to a site. * * Algorithm: Find a diamond that encloses all the points. * * This is however not unique, and we must find the one that **/ int max_x_plus_y = sites_x[0] + sites_y[0]; int min_x_plus_y = sites_x[0] + sites_y[0]; int max_x_minus_y = sites_x[0] - sites_y[0]; int min_x_minus_y = sites_x[0] - sites_y[0]; for(int i = 1; i < sites_x.length; i++) { if( (sites_x[i] + sites_y[i]) > max_x_plus_y) max_x_plus_y = sites_x[i] + sites_y[i];
|
