\(i\) 番目の親機が Wifi を提供する範囲は、 \(x_i - w_i \le x \le x_i + w_i\) もしくは \(y_i - w_i \le y \le y_i + w_i\) を満たすような点 \((x, y)\) の集合です。

すべての親機について、区間 \([x_i - w_i, x_i + w_i]\) を重ね合わせたもの、および、区間 \([y_i - w_i, y_i + w_i]\) を重ね合わせたものを考えると問題文の条件は「前者の集合が区間 \([0, W]\) を被覆する、もしくは、後者の集合が区間 \([0, H]\) を被覆する」という条件と同値です。もしもこの条件を満たすなら問題文の条件が満たされることは明らかで、また、もしもこの条件を満たしていない場合、\([0, W]\) のうち被覆されていないある点 \(x\) と \([0, H]\) のうち被覆されていないある点 \(y\) を取ると、 \((x, y)\) は街の内部もしくは境界であり、Wifi が提供されていない点なので、問題文の条件が満たされません。したがって、この同値な条件が満たされるかどうかを判定すればよいです。

区間の重ね合わせがある区間を被覆するかについては、例えば ABC256-Dなどと同様にイベントソートや imos 法を用いることなどで判定できます。計算量は例えば imos 法を用いた場合 \(O(N + H + W)\) です。