JOI春合宿2008 Belt
Belt はかなり面倒な幾何に見えますが、実は実装は比較的楽に書けます。
解法
動く歩道から距離D以下の範囲にある家を最大化したい。「動く歩道」を考えるのは面倒なので、幅2Dの帯を考え、その帯を動かして考える。すると、帯を平行移動することにより、帯の境界上に1点が存在するとしてよい。この点を固定して考え、それをすべての点に対して行うことで解を求める。
簡単のため固定した点を原点に平行移動する。すると、ある点が帯に含まれるということを、角θを用いて「動径が角θから角θ+πまで動くときの動径の動く側にあり、角θの動径が作る直線からの距離が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; }