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

面白かった

問題へのリンク

問題概要

二次元平面上に 個の点がある。これらの各点 に対し、

• 

を満たす点 に電波が届く。 から までの長方形区間全体に電波が届くかどうかを判定せよ。

制約

• 

考えたこと

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

• 個の区間 [ , ] が [ ] を覆う
• 個の区間 [ , ] が [ ] を覆う

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

#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;
}