public class Flee { boolean check(int[] x, int[] y, double r) { int n = x.length; for(int i = 0; i < n; i++) if(x[i]*x[i] + y[i]*y[i] <= r*r) return true; boolean linked[][] = new boolean[n][n]; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) <= 4*r*r) linked[i][j] = true; for(int start = 0; start < n; start++) { double[] maxVal = new double[n]; for(int i = 0; i < n; i++) maxVal[i] = -1000; maxVal[start] = 0; for(int iteration = 1; iteration <= n; iteration ++) { for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(linked[i][j]) { double delta = Math.atan2(y[j], x[j]) - Math.atan2(y[i], x[i]); if(Math.abs(delta + Math.PI * 2) < Math.abs(delta)) delta = delta + Math.PI * 2; else if(Math.abs(delta - Math.PI*2) < Math.abs(delta)) delta = delta - Math.PI * 2; maxVal[j] = Math.max(maxVal[j], maxVal[i] + delta); } } if(maxVal[start] >= 2 * Math.PI - 1e-9) return true; } return false; } public double maximalSafetyLevel(int[] x, int[] y) { double L = 0, R = 2000, M = 0; for(int iteration = 1; iteration <= 100; iteration ++) { M = (L + R) / 2; if(check(x, y, M)) R = M; else L = M; } return M; } }