AOJ 1132,PKU 1981 Circle and Points

問題概要

10x10の領域に半径1の点をN個置く。任意の位置にある半径1の円に最大で何個入るかを求めろ。

解法

分割統治法を用い、探索領域を減らしていく。
AOJ0090と全く同じ問題。

実装(C++)

#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
#define REP(i,x) for(int i=0;i<(int)(x);i++)
int ans=0;
struct Rect
{
    double x,y,size;
    int count;
    Rect(double x=0,double y=0,double size=0,int count=0):x(x),y(y),size(size),count(count){}
};
bool operator<(const Rect &a,const Rect &b)
{
    return a.count<b.count;
}
struct Point
{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y){}
    
};
priority_queue<Rect> que;
int N;
vector<Point> point;
const double EPS=1e-8;
#define p2(x) ((x)*(x))
void makerect(double x,double y,double size)
{
    int cnt=0,cnt2=0;
    x+=size*.5;
    y+=size*.5   
    REP(i,N){
	if(p2(point[i].x-x)+p2(point[i].y-y)<=p2(0.70711*size+1+EPS))
	    cnt++;
	if(p2(point[i].x-x)+p2(point[i].y-y)<=1.00+EPS)
	    cnt2++;
    }
    x-=size*.5;
    y-=size*.5;
    
    ans=max(ans,cnt2);
    if(cnt>ans)
	que.push(Rect(x,y,size,cnt));
}
void solve()
{
    que=priority_queue<Rect>();   
    que.push(Rect(0,0,10.0,N));
    while(!que.empty()){
	Rect t=que.top();
	que.pop();
	if(t.count<=ans)break;
	(makerect(t.x,t.y,t.size*.5));
	(makerect(t.x+t.size*.5,t.y,t.size*.5));
	(makerect(t.x,t.y+t.size*.5,t.size*.5));
	(makerect(t.x+t.size*.5,t.y+t.size*.5,t.size*.5));
    }
}
int main()
{
    for(;cin>>N,N;){
	point=vector<Point>(N);
	REP(i,N){
	    cin>>point[i].x>>point[i].y;
	}
	ans=1;
	solve();
	cout<<ans<<endl;
    }
}