[BOJ / 라인스위핑] 9318 위성사진

https://www.acmicpc.net/problem/9318

9318번: 위성 사진

 

9318 위성사진

 

알고리즘 : 세그먼트/인덱스 트리 + 라인스위핑

요즘 풀이하고 있는 라인스위핑 기초 문제입니다.

인덱스 트리 짜는 법이 헷갈려서 세그먼트 트리와 섞어서 짰습니다.

라인스위핑을 이용하여 수평선을 기점으로 구간트리를 구성하고 업데이트하여

넓이를 알아내는 방식입니다.

 

CHECK POINT

총 나올 수 있는 구간의 수는 MAX_N * 2개(모든 사각형의 변의 높이가 같지 않을 때)이므로

다른 세그먼트트리보다 더 큰 용량을 가진 트리를 구성해야합니다.

한 축이 1,000,000 까지이므로 모든 평면을 가렸을 때 결과값이 1,000,000^2으로 int형을 초과하므로

long long int를 이용하여 계산하였습니다.

 

 

 

 

 

 

 

 

 

< CODE >

// 9318 위성 사진

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define MAX 1005

struct Row
{
	int x;
	int sy;
	int ey;
	int isStart;
};

struct Node
{
	long long int sum;
	int cnt;
	int sy;
	int ey;
};

bool operator<(const Row & a, const Row & b)
{
	if(a.x == b.x)
		return a.isStart > b.isStart;
	
	return a.x < b.x;
}


Node tree[MAX * 10];
vector<Row> row;
vector<int> col;
Node init = {0,0,987654321,-1};

void clear()
{
	for(int i = 0; i < MAX * 10; i++)
		tree[i] = init;
	
	row.clear();
	col.clear();
}

void update(int idx, int left, int right, int isStart)
{
	if(right <= tree[idx].sy || tree[idx].ey <= left || tree[idx].sy == 987654321)
		return;
	else if(tree[idx].sy >= left && tree[idx].ey <= right)
	{
		tree[idx].cnt += isStart;
		
		if(tree[idx].cnt > 0)
			tree[idx].sum = tree[idx].ey - tree[idx].sy;
		else
			tree[idx].sum = tree[idx*2].sum + tree[idx*2+1].sum;
		
		return;
	}
	
	update(idx * 2, left, right, isStart);
	update(idx * 2 + 1, left, right, isStart);
	
	if(tree[idx].cnt > 0)
		tree[idx].sum = tree[idx].ey - tree[idx].sy;
	else
		tree[idx].sum = tree[idx*2].sum + tree[idx*2+1].sum;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int t;
	
	cin >> t;
	
	while(t--)
	{
		clear();
		
		int n;
		
		cin >> n;
		
		for(int i = 0; i < n; i++)
		{
			int sx, sy, ex, ey;
			
			cin >> sx >> sy >> ex >> ey;
			
			row.push_back({sx,sy,ey,1});
			row.push_back({ex,sy,ey,-1});
			col.push_back(sy);
			col.push_back(ey);
		}
		
		sort(row.begin(),row.end());
		sort(col.begin(),col.end());
		
		col.erase(unique(col.begin(),col.end()),col.end());
		
		int idx = 1;
		int end = col.size() - 1;
		
		while(idx < end)
			idx <<= 1;
		
		for(int i = 1; i < col.size(); i++)
		{
			tree[idx + i - 1] = {0,0,col[i-1],col[i]};		
		}
		
		for(int i = idx - 1; i > 0; i--)
		{
			tree[i].sy = min(tree[i*2].sy,tree[i*2+1].sy);
			tree[i].ey = max(tree[i*2].ey,tree[i*2+1].ey);
		}
		
		long long int result = 0;
		
		for(int i = 0; i < row.size(); i++)
		{
			if(i != 0)
				result += tree[1].sum * (row[i].x - row[i-1].x);
	
			update(1,row[i].sy,row[i].ey,row[i].isStart);
		}
		
		cout << result << '\n';
	}

	return 0;
}

시간 : 52ms

 

태그 : #9318 위성사진 #백준 위성사진