두 문제 다 plane sweaping 알고리즘을 사용하여 풀 수 있다.
plane sweaping 알고리즘: https://codedoc.tistory.com/421
plane sweeping - 직사각형 넓이합 구하기
plane sweeping 사각형 넓이 구하기 알고리즘 문제링크 : https://www.acmicpc.net/problem/3392 작성중... 아래 처럼 직사각형이 겹쳐졌을 때 색칠된 부분의 넓이 합을 구하는 것이 목표입니다. 먼저 각 직사각..
codedoc.tistory.com
plane sweaping 알고리즘의 핵심은 segment tree와 함께 sweaping 기법을 사용한다는 것이다.
자세한건 북서풍 문제로 알아보자.
행사장 대여 같은 경우에는 plane sweaping에서 아이디어를 착안해서 풀었다.
넓이의 합에 segment tree를 사용할 필요는 없다고 느껴, 이진 탐색 트리인 map으로 문제를 풀었다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
class Rect {
public:
int x1, y1, x2, y2;
};
class Line {
public:
Line() {
}
Line(int x, int y1, int y2, bool bStart) :
x(x), y1(y1), y2(y2), bStart(bStart) {
}
bool operator<(const Line& line) {
return x < line.x;
}
int x, y1, y2;
bool bStart;
};
class Segment {
public:
Segment() {
height = 0;
startX = 0;
count = 0;
}
int height;
int startX, count;
};
istream& operator>>(istream& is, Rect& rect) {
return is >> rect.x1 >> rect.y1 >>
rect.x2 >> rect.y2;
}
bool sort(const Rect& r1, const Rect& r2) {
return (r1.x1 != r2.x1) ? r1.x1 < r2.x1 : r1.x2 < r2.x2;
}
int main() {
int n;
cin >> n;
// 입력
vector<Rect> rects(n);
for (int i = 0; i < rects.size(); i++)
cin >> rects[i];
// LEFT, RIGHT 선 데이터 생성
vector<Line> lines; // x, bottom, top
for (int i = 0; i < rects.size(); i++) {
lines.push_back(Line(rects[i].x1, rects[i].y1, rects[i].y2, true));
lines.push_back(Line(rects[i].x2, rects[i].y1, rects[i].y2, false));
}
sort(lines.begin(), lines.end());
// Y축 기준 세그먼트 트리 생성
map<int, Segment> segmentMap; // y, Segment
for (int i = 0; i < rects.size(); i++) {
segmentMap.insert({ rects[i].y1, Segment() });
segmentMap.insert({ rects[i].y2, Segment() });
}
for (auto iter = segmentMap.begin(); true; ) {
auto prevIter = iter;
if (++iter == segmentMap.end()) break;
int y1 = prevIter->first;
int y2 = iter->first;
prevIter->second.height = y2 - y1;
}
segmentMap.erase(--segmentMap.end());
long long sum = 0;
for (int i = 0; i < lines.size(); i++) {
auto sIter = segmentMap.lower_bound(lines[i].y1);
auto eIter = segmentMap.lower_bound(lines[i].y2);
for (auto iter = sIter; iter != eIter; iter++) {
// cout << lines[i].x << " " << iter->first << endl;
if (lines[i].bStart) {
if (iter->second.count++ == 0)
iter->second.startX = lines[i].x;
}
else {
if (--iter->second.count == 0) {
sum += (long long)iter->second.height * (long long)(lines[i].x - iter->second.startX);
// cout << iter->second.startX << " ~ " << lines[i].x << ", " << iter->first << " ~ " << iter->second.height + iter->first << \
" = " << iter->second.height * (lines[i].x - iter->second.startX) << endl;
}
}
}
}
cout << sum << endl;
return 0;
}
북서풍 문제 같은 경우, X좌표를 기반으로 세그먼트 트리를 생성하고 맨 오른쪽 아래 좌표부터 sweaping을 하여 풀었다.
처음에는 세그먼트 트리의 인덱스와 X 좌표의 값이 다르다 보니 각 노드에 X 좌표의 범위를 새겨줬는데, 시간 초과가 나서 다른 방법을 써야 했다. 검색을 해보니 X좌표를 인덱스 매기는 식으로 압축하면 된다하여 그렇게 했다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>
#include <cstring>
using namespace std;
class SegmentTree {
public:
SegmentTree(int n) {
h = (int)ceil(log2(n));
int size = 2 << (h + 1);
arr = new int[size];
memset(arr, 0, sizeof(int) * size);
}
~SegmentTree() {
delete[] arr;
}
int get(int n) {
int index = (2 << h) + n;
int sum = 0;
// Leaf 노드 처리
sum += arr[index]++;
while (index > 0) {
// 위로 올라 감
int prevIndex = index;
index /= 2;
// 왼쪽에서 올라왔으면 오른쪽 값 더함
if (prevIndex % 2 == 0)
sum += arr[index * 2 + 1];
// Sum 올림
arr[index]++;
}
return sum;
}
int h;
int* arr;
};
class Point {
public:
int x, y;
int r;
};
int main() {
int c; cin >> c;
while (c-- > 0) {
int n; cin >> n;
// 입력
vector<Point> points(n);
for (int i = 0; i < n; i++)
cin >> points[i].x >> points[i].y;
// X 좌표 순서대로 인덱스 매기기
sort(points.begin(), points.end(), [](const Point& p1, const Point& p2) {
return p1.x < p2.x;
});
int rank = 1;
points[0].r = rank;
for (int i = 1; i < points.size(); i++) {
if (points[i - 1].x != points[i].x) rank++;
points[i].r = rank;
}
// X 좌표 기반 세그먼트 트리 생성
SegmentTree segmentTree(rank);
// 맨 오른쪽 아래 좌표부터 카운트 시작
sort(points.begin(), points.end(), [](const Point& p1, const Point& p2) {
return (p1.y != p2.y) ? p1.y < p2.y : p1.x > p2.x;
});
long long answer = 0;
for (int i = 0; i < n; i++)
answer += segmentTree.get(points[i].r);
cout << answer << "\n";
}
return 0;
}
시간 제한이 1초이다보니 자잘한 연산들도 다 최적화 해줘야 해서 불편했다...
그리고 처음에는 압축 방식을 unordered_map을 사용해서 했는데, 이 또한 O(kn)이라 시간 초과가 났다.
O(n)인 인덱스 매기는 방법이 유일한 방법인거 같다.
