Boj 2672) 여러 직사각형의 전체 면적 구하기

문제

백준 2672

방법 1

설명

사각형들의 모든 꼭짓점을 구한다. 그리고 그 꼭짓점으로 Grid 를 만든다. Grid 의 기본 사각형이 주어진 사각형 중 하나에 포함이 되면 넓이를 추가해준다.

시간 복잡도

O(\(\mathrm{N}^3\))

코드

struct RECT {
	double _l, _r, _t, _b;
	bool IsInside(double l, double r, double t, double b) const
	{
		return _l <= l && r <= _r && _t <= t && b <= _b;
	}
};
vector<RECT> rects;
vector<double> x, y;

int main()
{
	int n; cin >> n;
	for (int i = 0; i < n; i++)
	{
		double x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		x2 += x1; y2 += y1;
		x.push_back(x1); x.push_back(x2);
		y.push_back(y1); y.push_back(y2);
		rects.push_back(RECT{ x1, x2, y1, y2 });
	}

	sort(x.begin(), x.end());
	sort(y.begin(), y.end());

	double ans = 0;
	for (int i = 0; i < x.size() - 1; i++)
		for (int j = 0; j < y.size() - 1; j++)
		{
			bool bAble = false;
			for (RECT& r : rects)
				if (r.IsInside(x[i], x[i + 1], y[j], y[j + 1]))
				{
					bAble = true;
					break;
				}
			if (bAble) ans += (x[i + 1] - x[i]) * (y[j + 1] - y[j]);
		}

	double tmp;
	modf(ans, &tmp) ? cout.precision(2) : cout.precision(0);
	cout.setf(std::ios_base::fixed, std::ios_base::floatfield);
	cout << ans;
}

방법 2

설명

bitmask 를 쓴 Plain Sweeping 을 사용했지만 핵심은 이게 아니다.

출력은 소숫점 2자리에서 반올림이 아닌 버림을 요구하고, 무엇보다 주어진 수가 최대 소숫점 한자리라는 제한이 있다. 그래서 각 변에 10을 곱한 후에 구한 넓이에 100을 나눠도 같은 답이 나온다.

시간 복잡도

O(\(\mathrm{20000}^2\))

코드

using ii = pair<int, int>;
const int MAX_IN = 20001;
int masks[MAX_IN];
vector<ii> Begins[MAX_IN], Ends[MAX_IN];

int main()
{
	int n; cin >> n;
	for (int i = 0; i < n; i++)
	{
		double x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		x1 *= 10; x2 *= 10; y1 *= 10; y2 *= 10;
		x2 += x1; y2 += y1;
		Begins[(int)y1].push_back({ x1, x2 });
		Ends[(int)y2].push_back({ x1, x2 });
	}

	long long ans = 0;

	for (int i = 0; i < MAX_IN; i++)
	{
		for (auto& b : Begins[i])
			for (int j = b.first; j < b.second; j++)
				masks[j]++;
		for (auto& b : Ends[i])
			for (int j = b.first; j < b.second; j++)
				masks[j]--;

		int width = 0;
		for (int j = 0; j < MAX_IN; j++)
			if (masks[j]) width++;

		ans += width;

	}

	double tmp, res = (double)ans * 0.01;
	modf(res, &tmp) ? cout.precision(2) : cout.precision(0);
	cout.setf(std::ios_base::fixed, std::ios_base::floatfield);
	cout << res;
}