JOI春合宿2008 Belt

Belt はかなり面倒な幾何に見えますが、実は実装は比較的楽に書けます。

解法

動く歩道から距離D以下の範囲にある家を最大化したい。「動く歩道」を考えるのは面倒なので、幅2Dの帯を考え、その帯を動かして考える。すると、帯を平行移動することにより、帯の境界上に1点が存在するとしてよい。この点を固定して考え、それをすべての点に対して行うことで解を求める。
簡単のため固定した点を原点に平行移動する。すると、ある点が帯に含まれるということを、角θを用いて「動径が角θから角θ+πまで動くときの動径の動く側にあり、角θの動径が作る直線からの距離がD以下」と定めることができる。θが[0, 2π)を動くときの、含まれる点の最大値を求めればよい。
極座標において と表される点が、いつ帯に含まれるかを考える。図を描くと、r <= D のときは[α-π, α]が、r > D のときは[α-π, α-π+δ], [α-δ, α] (但し、sin δ = r / D) が条件を満たすことがわかる。後は、点が帯から出たり入ったりというイベントをソートして、θを0から2πまで動かしてやればよい。
この方法による計算量は O(N^2 log N) で、三角関数の計算をO(N^2)回必要とするものの時間制限がかなり緩いので通る。

コード

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int N, x[1000], y[1000];
double D;
const double PI = 3.1415926535897932384626433;
vector<pair<double, int> > action;

void add_act(double v, int a)
{
	if(v<0) v += 2*PI;
	if(v>2*PI) v -= 2*PI;
	action.push_back(make_pair(v, a));
}

int solve(int p)
{
	action.clear();
	int sum = 0;
	for(int i=0;i<N;i++) if(i!=p){
		int xv=x[i]-x[p], yv=y[i]-y[p];
		double theta = atan2((double)yv, (double)xv);
		if(theta<0) theta += 2*PI;
		if(0<=yv && yv<=D) sum++;
		if(xv*xv+yv*yv<=D*D){
			add_act(theta-PI, 0);
			add_act(theta+1e-7, 1);
		}else{
			double delta = asin(D / sqrt((double)(xv*xv+yv*yv)));
			add_act(theta-PI, 0);
			add_act(theta-PI+delta+1e-7, 1);
			add_act(theta-delta, 0);
			add_act(theta+1e-7, 1);
		}
	}
	sort(action.begin(), action.end());

	int ret = sum;
	for(int i=0;i<action.size();i++) if(action[i].first > 1e-8){
		if(action[i].second == 0){
			sum++;
			ret = max(ret, sum);
		}else sum--;
	}
	return ret + 1;
}

int main()
{
	scanf("%d%lf", &N, &D);
	D *= 2;
	for(int i=0;i<N;i++) scanf("%d%d", x+i, y+i);

	int ret = 0;
	for(int i=0;i<N;i++) ret = max(ret, solve(i));

	printf("%d\n", ret);

	return 0;
}