028.md

028 - Cluttered Paper (★4)

解答

#include <iostream>
#include <vector>

int main()
{
	// N 枚の長方形の紙
	int N;
	std::cin >> N;

	constexpr int W = 1001;
	constexpr int H = 1001;
	std::vector<std::vector<int>> grid(H, std::vector<int>(W));

	///////////////////////
	//
	// 二次元いもす法
	//

	for (int i = 0; i < N; ++i)
	{
		int lx, ly, rx, ry;
		std::cin >> lx >> ly >> rx >> ry;

		++grid[ly][lx];
		++grid[ry][rx];
		--grid[ly][rx];
		--grid[ry][lx];
	}

	// X 方向の累積和
	for (int y = 0; y < H; ++y)
	{
		for (int x = 1; x < W; ++x)
		{
			grid[y][x] += grid[y][x - 1];
		}
	}

	// Y 方向の累積和
	for (int x = 0; x < W; ++x)
	{
		for (int y = 1; y < H; ++y)
		{
			grid[y][x] += grid[y - 1][x];
		}
	}

	//
	///////////////////////

	// 枚数ごとの面積
	// counts[0] は 0 枚重なっている部分の面積
	// counts[1] は 1 枚重なっている部分の面積
	// counts[2] は 2 枚重なっている部分の面積
	// ...
	std::vector<int> counts(N + 1);

	for (const auto& row : grid)
	{
		for (const auto& n : row)
		{
			++counts[n];
		}
	}

	// 1 枚 ～ N 枚 重なっている部分の面積について出力
	for (int i = 1; i <= N; ++i)
	{
		std::cout << counts[i] << '\n';
	}
}