[2018 홍익대학교 프로그래밍 경진대회] 16396번 선 그리기

문제

준용이의 조카 준섭이는 크레파스로 한 직선에 평행한 여러 개의 선분을 그리고 있었다.

준섭이의 모습을 보고 있던 준용이는 준섭이가 그린 모든 선들을 직선 좌표에 투사(projection)했을 때 투사된 선들의 길이 합이 궁금하였다.

준용이에게 잘 보여야하는 여러분은 준용이의 궁금증을 해결하기 위해 프로그램을 구현해주자.

입력

첫 번째 줄에는 준섭이가 그린 선의 개수 N이 입력된다.

두 번째 줄부터 N+1 번째 줄까지는 준섭이가 그린 선의 시작 좌표 Xi와 끝 좌표 Yi 가 순서대로 주어진다. Xi 와 Yi 는 정수이며, 띄어쓰기로 구분된다.

N의 범위는 1부터 10,000까지이다. 선의 시작 좌표와 끝 좌표는 1부터 10,000까지의 자연수이다.

출력

직선 좌표에 투사된 선의 총 길이 합을 정수로 출력한다. 

 

스위핑 알고리즘 

갱신된 마지막 r,l에 대해서 합해주고 끝내야함.

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<stack>
#include<set>
#include<map>
using namespace std;

const int INF = 987654321;
int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	int N;
	cin >> N;
	vector<pair<int, int> > vec;
	for (int i = 0; i < N; i++)
	{
		int a, b;
		cin >> a >> b;
		vec.push_back({ a,b });
	}
	
	sort(vec.begin(), vec.end());
	int l = -INF;
	int r = -INF;
	long long res = 0;
	for (int i = 0; i < vec.size(); i++)
	{
		if (vec[i].first > r)
		{
			res += r - l;
			r = vec[i].second;
			l = vec[i].first;
		}
		else
		{
			r = max(r, vec[i].second);
		}
	}
	res += r - l;
	cout << res << endl;
}