[BOJ/백준] 2170 - 선 긋기

2170번: 선 긋기

---

선 겹칠 때마다 합치기

 

+

 

선 좌표 정렬

---

---

• 제목

선 긋기

---

• 조건

시간 제한 : 1 초

메모리 제한 : 192 MB 

---

• 문제

매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.

이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다.

---

• 입력

첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.

---

• 출력

첫째 줄에 그은 선의 총 길이를 출력한다.

---

예제 입력1	예제 출력1
4 1 3 2 5 3 5 6 7	5

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
#define endl '\n'
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int sz, start, end;
    cin >> sz;
	vector<pair<int, int> > lines, vec;
    while(sz--){
    	cin >> start >> end;
    	lines.push_back(make_pair(start, end));
	}
	sort(lines.begin(), lines.end());
	sz = lines.size();
	for(int k = 0 ; k < lines.size() ; k++){
		start = lines[k].first;
		end = lines[k].second;
    	bool lineCheck = false;
    	for(int n = 0 ; n < vec.size() ; n++){
    		int std_s = vec[n].first;
    		int std_e = vec[n].second;
    		if((std_s <= start && start <= std_e) || (std_s <= end && end <= std_e)){
    			if(std_s <= start && start <= std_e && std_e < end){
    				vec[n].second = end;
				}
				else if(std_s <= end && end <= std_e && start < std_s){
    				vec[n].first = start;
				}
				else if(start <= std_s && std_e <= end){
					vec[n].first = start;
					vec[n].second = end;
				}
				lineCheck = true;
    			break;
			}
		}
		if(!lineCheck) vec.push_back(make_pair(start, end));
	}
	int sum = 0;
	for(int n = 0 ; n < vec.size() ; n++) sum += vec[n].second - vec[n].first;
	cout << sum << endl;
    return 0;
}