いもす法をバグらせるのをやめなさ~い!!
AOJ 2600 Koto Distance
問題概要
南北にHメートル、東西にWメートルの長方形の領域内にN個のWifi の親機を設置する。入力で親機の座標及びその親機のカバーできるKoto範囲が与えられるので、設置した親機によってこの長方形の領域が全てカバーできるか判定する。なお、Koto距離は任意の2地点、に対してによって定義される。
制約
同一座標に親機は複数存在しない
考察
- 配列で持てないので工夫が必要になる。
- 親機の座標が与えられた時に、までの範囲内では親機はy方向を全てカバーでき、同様にまでの範囲内では親機はx方向を全てカバーできることが分かる。
- カバーできる範囲を塗りつぶしたいけど配列に持てない・・・・でも塗りつぶし系はいもす法が使える・・・・
- x方向とy方向に分けて見れば配列に持つことができるのでは??これならいもす法が使えそう・・・・
- では、判定は???・・・・・・行か列のどちらかが全て覆われていれば全部覆われているとみなせる!!
- よって行と列で別々にいもす法で塗りつぶしてどちらか一方が全て覆われていればYes、そうでないならNoを出力すればよい。
- なお、配列の添え字周りでバグらせてしまったので反省(ア)
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<utility> #include<string> #include<cmath> #include<cstring> #include<queue> #include<map> #include<climits> #include<set> using namespace std; typedef pair<int, int> pii; typedef long long int ll; typedef pair<ll, ll> pll; int dx[4] = { 1,0,0,-1 }; int dy[4] = { 0,1,-1,0 }; #define MOD 1000000007 #define ARRAY_MAX 100005 const int INF = 1e9 + 7; int imos[ARRAY_MAX];//y方向 int imos2[ARRAY_MAX];//x方向 int main() { ios::sync_with_stdio(false); cin.tie(0); int n, w, h; cin >> n >> w >> h; for (int i = 0; i < n; i++) { int x, y, z; cin >> x >> y >> z; imos[max(y - z, 0)]++; imos[min(y + z, h + 1)]--; imos2[max(0, x - z)]++; imos2[min(x + z, w + 1)]--; } for (int i = 0; i <= h; i++) { imos[i + 1] += imos[i]; } for (int i = 0; i <= h; i++) { imos2[i + 1] += imos2[i]; } bool flag = true; bool flag2 = true; for (int i = 0; i < h; i++) { //縦方向 if (imos[i] <= 0) { flag = false; break; } } for (int i = 0; i < w; i++) { //横方向 if (imos2[i] <= 0) { flag2 = false; break; } } if (flag || flag2) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0; }