PKU1981

Circle and Points
2004年国内予選の問題
ジャンルは幾何学
詳しい解説はこちらをどうぞ。

プログラムプロムナードの解説の分割統治法を理解して実装すれば解けます。
あとJAVAの場合、優先度つき待ち行列の比較のためにComparableを実装することがポイント。

ソースは以下の通り

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	Scanner scan = new Scanner(System.in);
	int n, ans;
	Point p[] = new Point[300];
	PriorityQueue<Box> pq = new PriorityQueue<Box>();
	double r2 = Math.sqrt(2.0);
	double EPS = (1e-6);
	
	class Point{
		double real;
		double imag;		
		
		Point(double r, double i){
			real = r;
			imag = i;
		}
	}
	
	class Box implements Comparable<Box>{
		double x, y, size;
		int cnt;
		
		Box(double x1, double y1, double s, int c){
			x = x1;
			y = y1;
			size = s;
			cnt = c;
		}

		public int compareTo(Box o) {
			return this.cnt - o.cnt;
		}
	}
	
	Point subPoint(Point p1, Point p2){
		Point p = new Point((p1.real - p2.real),(p1.imag - p2.imag));
		return p;
	}
	
	void save(double x, double y, double size){
		Box b = new Box(x, y, size, 0);		
		int cnt = 0;
		Point c = new Point((x + size/2.0), (y + size/2.0));
		double er = (r2*size + 1.0) * (r2*size + 1.0);
		
		for (int i=0; i<n; i++) {
		    Point tmp = subPoint(c, p[i]);
		    double d = tmp.real * tmp.real + tmp.imag * tmp.imag;
		    if (d < 1.0 + EPS) { cnt++; }
		    if (d < er + EPS) { b.cnt++; }
		  }
		
		if (cnt > ans) {ans = cnt;}
		if (b.cnt > ans) {pq.add(b);}
	}
	
	Main(){
		for(;;){
			if((n = scan.nextInt()) == 0) break;
			for(int i = 0; i < n; i++){
				p[i] = new Point(scan.nextDouble(), scan.nextDouble());
			}
			
			Box start = new Box(0.0, 0.0, 10.0, n);
			pq.add(start);
			ans = 1;
			
			while(!pq.isEmpty()){
				Box b = pq.poll();
				if (b.cnt > ans) {
			        double half = b.size / 2.0;
			        save(b.x, b.y, half);
			        save(b.x+half, b.y, half);
			        save(b.x, b.y+half, half);
			        save(b.x+half, b.y+half, half);
			      }
			}
			System.out.println(ans);
		}
	}
	
	public static void main(String[] args) {
		new Main();
	}
}