B09 - Papers

atcoder.jp

ABとCDが座標というのを理解していなくて、1まわり大きい面積を計算してしまっていた。実際に手計算して気付けたけど、結構嵌まってしまったな。

var N = int.Parse(Console.ReadLine()!);
var A = new int[N];
var B = new int[N];
var C = new int[N];
var D = new int[N];
for (var i = 0; i < N; i++)
{
    var ABCD = Console.ReadLine()!.Split(' ').Select(x => int.Parse(x)).ToList();
    (A[i], B[i], C[i], D[i]) = (ABCD[0], ABCD[1], ABCD[2], ABCD[3]);
}
const int HEIGHT = 1500 + 1;
const int WIDTH = 1500 + 1;
var X = new int[HEIGHT, WIDTH];
for (var i = 0; i < N; i++)
{
    var (x1, y1, x2, y2) = (A[i], B[i], C[i], D[i]);
    X[y1, x1]++;
    X[y1, x2]--;
    X[y2, x1]--;
    X[y2, x2]++;
}

var Z = new int[HEIGHT, WIDTH];
for (var y = 0; y < HEIGHT; y++)
{
    for (var x = 0; x < WIDTH; x++)
    {
        Z[y, x] = X[y, x];
        if (0 < x)
        {
            Z[y, x] += Z[y, x - 1];
        }
    }
}
for (var x = 0; x < WIDTH; x++)
{
    for (var y = 0; y < HEIGHT; y++)
    {
        if (0 < y)
        {
            Z[y, x] = Z[y - 1, x] + Z[y, x];
        }
    }
}

var answer = 0;
for (var y = 0; y < HEIGHT; y++)
{
    for (var x = 0; x < WIDTH; x++)
    {
        if (0 < Z[y, x])
        {
            answer++;
        }
    }
}
Console.WriteLine(answer);