AOJ 2600: Koto Distance

問題:

Koto Distance | Aizu Online Judge

街全体が無線LANルータによって定められたKoto距離以内に収まっているかを考える。

解法:

上の図のように、(x,y)からwのKoto距離以内の範囲というのは、x-w列目からx+w列目までと、y-w行目からy+w行目までである。そのため個々の格子点について調べる必要はなく、行または列がカバーされているか考えれば良い。

行または列のいずれかにカバーされていない範囲があったとしても、他方が全てカバーされている場合、街全体がカバーされていると言える。逆に、カバーされていない行と列が両方存在する場合、街の中にカバーされていない領域が存在する。

カバーされているかどうかを調べるために累積和（いもす法 - いもす研 (imos laboratory)）を使う。カバー範囲の左側の境界線で+1し、右側の境界線で-1する。

解答:

import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();// 親機の数
        int W = scanner.nextInt();
        int H = scanner.nextInt();

        int[] width = new int[W + 1];
        int[] height = new int[H + 1];
        for (int i = 0; i < N; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int w = scanner.nextInt();

            int lowx = Math.max(0, x - w);
            int highx = Math.min(W, x + w);

            width[lowx]++;
            width[highx]--;

            int lowy = Math.max(0, y - w);
            int highy = Math.min(H, y + w);

            height[lowy]++;
            height[highy]--;

        }
        scanner.close();

        int cover = 0;
        boolean isCovered = true;
        for (int i = 0; i < W; i++) {
            cover += width[i];
            if (cover <= 0) {
                isCovered = false;
            }
        }

        cover = 0;
        for (int i = 0; i < H; i++) {
            cover += height[i];
            if (cover <= 0 && !isCovered) {
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");

    }
}