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; } }