Mars Maps
Problem
https://www.acmicpc.net/problem/3392
Summary
겹친 직사각형들의 총 넓이 구하기
지도의 수 N(1 ≤ N ≤ 10,000), (x1, y1)와 (x2, y2)은 직사각형의 왼쪽 아래 좌표와 오른쪽 위 좌표
x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ 30,000, 0 ≤ y1 < y2 ≤ 30,000)
Idea
native
N^3
for (x 만큼){
for (y 만큼) {
for (직사각형 개수 n만큼) {
if (x,y가 큰 직사각형에 포함되는지) {
sum update
}
}
}
}
flood fill
직사각형에 카운트 1을 채운다. 중복된 영역은 카운트 +1 을 해 최종적으로 카운트 1을 센다
plane sweeping with segment tree
- 각각의 직사각형의 시작 면(왼쪽면)과 끝면(오른쪽 면)을 list에 담아 x축으로 오름차순 정렬
시작면 x1,y1,y2,1
끝면 x2,y1,y2,-1
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
points[2*i] = new Point(x1, y1, y2, 0);
points[2*i+1] = new Point(x2, y1, y2, 1);
}
Arrays.sort(points);
-
x좌표를 sweep 하면서 넓이를 구해간다
-
x를 하나 꺼내 세로선 업데이트
세로선이 시작선일 경우, 해당 구간의 노드 값을 1 증가
새로선이 끝 선일 경우, 해당 구간의 노드 값을 1 감소 -
면적을 구한다 (높이= leaf 노드가 1 이상인 개수 query) (x - 이전 x) * 높이
업데이트 구간이 크므로 lazy update를 고려해야한다
대표값을 만나면 1로 마킹 후 업데이트 하지 않는다 (=node 구간크기)
void update(int node, int s, int e, int l, int r, int val) {
if (r < s || e < l) {
return;
}
if (l <= s && e <= r) {
tree[node][1] += val; // tree[node][1]: 중복 카운트, tree[node][0]: 1의 개수
} else {
int mid = (s + e) >> 1;
update(node * 2, s, mid, l, r, val);
update(node * 2 + 1, mid + 1, e, l, r, val);
}
if (tree[node][1] == 0) {
if (s == e)
tree[node][0] = 0;
else
tree[node][0] = tree[node * 2][0] + tree[node * 2 + 1][0];
} else {
tree[node][0] = e - s + 1;
}
}