PKU1981
id:succeedに煽られてやってみたところ、
Scanner.nextDoubleが恐ろしく遅いとしか思えない結果になった。
http://acm.pku.edu.cn/JudgeOnline/problemstatus?problem_id=1981&language=2&orderby=time
BufferedReaderを使ったこと以外何の変哲もないコードだし。
import java.io.*; class Main{ private static double[] xs = new double[300], ys = new double[300]; private static int n; public static void main(String[] argv) throws Exception{ BufferedReader r = new BufferedReader(new InputStreamReader(System.in)); while((n=Integer.parseInt(r.readLine())) > 0){ for(int i=0; i<n; ++i){ String[] ss = r.readLine().split(" "); xs[i] = Double.parseDouble(ss[0]); ys[i] = Double.parseDouble(ss[1]); } int max = 1; for(int i=0; i<n; ++i){ double xi = xs[i], yi = ys[i]; for(int j=i+1; j<n; ++j){ max = Math.max(max, solve1(xi, yi, xs[j], ys[j])); } } System.out.println(max); } } private static int solve1(double x1, double y1, double x2, double y2){ final double small = 0.000001; double dx = x2-x1, dy = y2-y1; double dd = dx*dx + dy*dy; if(dd > 4){return 0;} double mx = (x1+x2)/2, my = (y1+y2)/2; double hd = Math.sqrt(1/dd - 0.25); double hx = dy*hd, hy = dx*hd; double cx1 = mx + hx, cx2 = mx - hx, cy1 = my - hy, cy2 = my + hy; int a1=0, a2=0; for(int i=0; i<n; ++i){ double x = xs[i], y = ys[i]; double dx1 = x - cx1, dx2 = x - cx2, dy1 = y - cy1, dy2 = y - cy2; if(dx1*dx1+dy1*dy1 <= 1 + small){++a1;} if(dx2*dx2+dy2*dy2 <= 1 + small){++a2;} } return Math.max(a1, a2); } }