けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 2600 Koto Distance (JAG 夏合宿 2013 day2-A)

面白かった

問題へのリンク

問題概要

二次元平面上に  N 個の点がある。これらの各点  (x_{i}, y_{i}) に対し、

  •  \min(|x - x_{i}|, |y - y_{i}|) \le D_{i}

を満たす点  (x, y) に電波が届く。 (0, 0) から  (X, Y) までの長方形区間全体に電波が届くかどうかを判定せよ。

制約

  •  1 \le N \le 10^{5}

考えたこと

全体を覆っているとき、以下のいずれかは成立していることがわかる

  •  N 個の区間 [  x_{i} - D_{i},  x_{i} + D_{i} ] が [  0, X ] を覆う
  •  N 個の区間 [  y_{i} - D_{i},  y_{i} + D_{i} ] が [  0, Y ] を覆う

これらのどちらかを満たすかどうかを判定する。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using pll = pair<long long, long long>; // (right edge, damage)

int N;
long long X, Y;
vector<pll> xin, yin;

bool isok(vector<pll> v, long long r) {
    long long cur = 0;
    for (int i = 0; i < v.size(); ++i) {
        if (cur < v[i].first) return false;
        chmax(cur, v[i].second);
    }
    if (cur < r) return false;
    return true;
}

int main() {
    cin >> N >> X >> Y;
    xin.resize(N), yin.resize(N);
    for (int i = 0; i < N; ++i) {
        long long x, y, d;
        cin >> x >> y >> d;
        xin[i] = {x-d, x+d};
        yin[i] = {y-d, y+d};
    }
    sort(xin.begin(), xin.end());
    sort(yin.begin(), yin.end());

    if (isok(xin, X) || isok(yin, Y)) cout << "Yes" << endl;
    else cout << "No" << endl;
}