UVaLive

UvaLive2519 Radar Installation

題目連結

  • 題意：現在有 $N$ 個點在 $X$ 軸上方，現在要在 $X$ 軸建立一些雷達，雷達可以覆蓋半徑 $d$ 以內的點，問最小需要幾個雷達。
  • 題解：先求 $N$ 個點為中心，半徑為 $d$ 以內，和 $X$ 軸的交區間(如果沒有和 $X$ 軸有交界則無解)。這樣這題題目就變成了區間選點問題。
    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
    68
    69
    70
    71
    72
    73
    74
    #pragma GCC optimize("O2")
    #include <bits/stdc++.h>
    using namespace std;
    using LL = long long;
    using ULL = unsigned long long;
    using PII = pair<int, int>;
    using PLL = pair<LL, LL>;
    using VI = vector<int>;
    using VVI = vector<vector<int>>;
    const int INF = 1e9;
    const int MXN = 0;
    const int MXV = 0;
    const double EPS = 1e-9;
    const int MOD = 1e9 + 7;
    #define MP make_pair
    #define PB push_back
    #define F first
    #define S second
    #define FOR(i, L, R) for (int i = L; i < (int)R; ++i)
    #define FORD(i, L, R) for (int i = L; i > (int)R; --i)
    #define IOS                                                                    \
        cin.tie(nullptr);                                                          \
        cout.tie(nullptr);                                                         \
        ios_base::sync_with_stdio(false);
    struct Range
    {
        double L, R;
        bool operator<(Range &rhs) const { return R < rhs.R; }
    };

    int main()
    {
        IOS;
        int n, ti = 0;
        double d;
        vector<Range> ranges;
        while (cin >> n >> d, n)
        {
            double x, y;
            bool ok = true;
            ranges.clear();
            FOR(i, 0, n)
            {
                cin >> x >> y;
                double dis = sqrt(d * d - y * y);
                if (y > d)
                {
                    ok = false;
                }
                else
                {
                    ranges.push_back({x - dis, x + dis});
                }
            }
            if (!ok)
            {
                cout << "Case " << ++ti << ": " << -1 << '\n';
                continue;
            }
            sort(ranges.begin(), ranges.end());
            int ans = 1;
            double curR = ranges[0].R;
            // FOR(i, 0, n) { cout << ranges[i].L << ":" << ranges[i].R << '\n'; }
            FOR(i, 1, n)
            {
                if (ranges[i].L > curR)
                {
                    ++ans;
                    curR = ranges[i].R;
                }
            }
            cout << "Case " << ++ti << ": " << ans << '\n';
        }
    }

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Recommended Posts