いもす法をバグらせるのをやめなさ~い!!

AOJ 2600 Koto Distance

問題概要

南北にHメートル、東西にWメートルの長方形の領域内にN個のWifi の親機を設置する。入力で親機の座標(x_{i},y_{i})及びその親機のカバーできるKoto範囲w_{i}が与えられるので、設置した親機によってこの長方形の領域が全てカバーできるか判定する。なお、Koto距離は任意の2地点(x_{i},y_{i})(x_{i+1},y_{i+1})に対してmin(|x_{i}-x_{i+1}|,|y_{i}-y_{i+1}|)によって定義される。

制約

1\leq N,H,W \leq 10^{5}
1\leq x_{i} \leq W
1\leq y_{i} \leq H
1\leq w_{i} \leq  10^{5}
同一座標に親機は複数存在しない

考察

  • 配列で持てないので工夫が必要になる。
  • 親機の座標(x_{i},y_{i})が与えられた時に、x_{i} \pm w_{i}までの範囲内では親機はy方向を全てカバーでき、同様にy_{i} \pm w_{i}までの範囲内では親機は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;
}