[BOJ백준] 2170 선 긋기

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

2170번: 선 긋기

---

문제해설

이 문제의 분류는 "라인스위핑" 입니다.

라인스위핑 알고리즘을 사용하여 중구난방으로 입력된 좌표들을 

어떤 기준에 의해 정렬한뒤에

O(N)으로 처음부터 끝까지 쓰~윽 처리해주시면 됩니다.

기준을 잡는 것에 있어서 여러가지 방법이 있을 수 있습니다.

저는 x축 을 기준으로 정렬한뒤에 현재까지 선을 그은 마지막 위치를 저장하여 처리 했습니다. 

 

---

전체코드

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

typedef pair<int, int> pii;
vector<pii> vec;

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		int a, b; cin >> a >> b;
		if (b < a) {
			int t = b;
			b = a;
			a = t;
		}
		vec.push_back({ a,b });
	}
	int e = -(1e9+1);
	int ans = 0;
	sort(vec.begin(), vec.end());
	for (int i = 0; i < N; i++) {
		if (e == -(1e9 + 1)) {
			e = vec[i].second;
			ans += e - vec[i].first;
		}

		if (vec[i].first < e) {
			int diff = vec[i].second - e;
			ans += (diff > 0) ? diff : 0;
			e = max(e,vec[i].second);
		}
		else if (vec[i].first >= e) {
			ans += vec[i].second - vec[i].first;
			e = vec[i].second;
		}
	}
	cout << ans << "\n";
}