AOJ 2600 - Koto Distance
解法
サンプルの図がわかりやすいのですが、ある座標(x,y)から距離w以内に効果がある場合、
(x-w,p)~(x+w,p)および(p,y-w)~(p,y+w)の範囲に効果があることになります。ここで、pは任意の数字になります。これは、横についてx-w~x+wの範囲を、縦についてy-w~y+wの範囲をカバーしていることになります。
そして、都市全体をカバーしきるには、
横、もしくは縦にのみ注目したときに、全てのx(もしくはy)座標がカバーされている、ということが必要になります。
なので、全ての入力を、縦、および横に分解してカバーしている範囲を調べ、全てをカバーしきれているかどうか判定すればいいことになります。
これは普通の累積和を使うと間に合わないですが、いもす法を使うとうまくいきます。
sum[i] = 座標iをカバーしている親機の個数とすると、
ある親機がa ~ bという範囲をカバーしているとき、
sum[a] += 1,sum[b+1] -=1
してあげて、sum[0]から順番に累積和をとると、sum[i]が1以上であればその座標がカバーできていることになります。
そして、コーナーケースが存在します。
サンプルで言うと、
2 10 10
1 1 3
10 10 5
のようなケースです。
このケースでは、縦に注目したとき(横でも同じですが)、1~4,5~10はカバーできているのですが、4~5の部分がカバーしきれていません。
そこで、4.5という部分も判定する必要があります。
これは、配列の要素を2w(もしくは2h)というように2倍してあげることで対応できます(座標すべてを2倍にすることで、拡張してあげます)。
