Algoogle

Algorithm for Programming Contest

JOI 春合宿 2008 Belt

Category: JOI Tag: geometry

Belt

問題概要


平面上に直線を引いたときに, その直線から距離d以内に存在する点の数を最大化しろ

解法


1点を固定して中心と考える.
その点を通る直線から左右どちらかに幅2dをとって360度回してやって, 各イベント点でいくつ中に入ってきてるかカウントしてやれば良い.

はじめ帯がx軸から上に幅2dとった状態からスタートするとする.
イベントは点が帯に入るときと出るときで, 点の偏角をth, 原点からの距離をrとすると

  • th-asin(d/r) : 帯に入る
  • th : 帯から出る
  • th+pi : 帯に入る
  • th+pi+asin(d/r) : 帯から出る

の4つが考えられる.
またrがd以下の場合帯から出られない部分があるので

  • th+pi : 帯に入る
  • th : 帯から出る

の2つだけになる.
あとははじめから帯に入っている場合に注意してイベント(偏角)順にソートして順番に見ていけばよい

コード


(Belt.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
typedef pair<double, int> pdi;
const double pi = acos(-1.);
const double eps = 1e-7;
int n, x[1024], y[1024];
double d;

inline double sq(double a){ return a*a;}
inline double fit(double th){
        while(th < 0) th += 2*pi;
        while(th > 2*pi) th -= 2*pi;
        return th;
}

int solve()
{
        d *= 2;
        int ans = 1;
        for (int i = 0; i < n; i++) {
                vector<pdi> events;
                int sat = 1;
                for (int j = 0; j < n; j++) {
                        if(j == i) continue;
                        const int px = x[j]-x[i], py = y[j]-y[i];
                        const double r = sqrt(sq(px)+sq(py)), th = atan2(py,px), dth = asin(d/r);
                        const double in1 = fit(th-dth-eps), in2 = fit(th+pi-eps),
                                     out1 = fit(th+eps), out2 = fit(th+pi+dth+eps);

                        if(r < d+eps) {
                                events.push_back(pdi(in2,1));
                                events.push_back(pdi(out1,-1));
                        }
                        else {
                                events.push_back(pdi(in1,1));
                                events.push_back(pdi(out1,-1));
                                events.push_back(pdi(in2,1));
                                events.push_back(pdi(out2,-1));
                        }
                        if(0 <= py and py <= d) sat++;
                }
                sort(begin(events),end(events));
                ans = max(ans, sat);
                for(auto &e: events) {
                        sat += e.second;
                        ans = max(ans, sat);
                }
        }

        return ans;
}

void input()
{
        cin >> n >> d;
        for (int i = 0; i < n; i++)
                cin >> x[i] >> y[i];
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments