보이는 산맥
문제
맑은 날 울릉도에서 태백산맥을 바라보면 수평선 위로 N개의 산봉우리가(1 ≤ N ≤ 100,000) 보인다.
다음은 N = 5인 경우의 예이다.
1
2
3
4
/\
/\ / \ /\
/ \/\ /\/ \/ \
/ \ \ / \ / \ ----------------------------- 각각의 산들은 높이가 밑변 길이의 2배인 이등변삼각형이다. 산은 밑변 꼭짓점의 정수 x좌표 두 개로 표현된다.
울릉도에서 바라본 산맥의 보이는 면적을 계산하여라.
입력
첫째 줄에 N이 입력된다. 둘째 줄부터 N+1번째 줄까지, 각각의 줄에는 산 하나를 표현하는 왼쪽 꼭짓점의 x좌표,
아래쪽 꼭짓점의 x좌표가 공백을 사이에 두고 입력된다.
입력으로 주어지는 x좌표는 32767보다 작거나 같은 자연수이다.
출력
첫째 줄에 산맥의 보이는 면적을 출력한다. 답은 부호 있는 32비트 정수 범위 안에 있다.
1
2
3
4
5
6
7
8
9
10
예제 입력 1
5
2 7
6 9
12 15
14 21
20 25
예제 출력 1
114
풀이
산들이 그려지고, 겹치는 부분을 빼면 된다.
헷갈렸던 것이 정렬을 해도 겹치는 부분이 많이 생길 수 있나? 였는데 아니었다.
어떻게 해도 산들의 기울기가 똑같기 때문에 한 번에 한 개의 삼각형만 겹친다는 것을 깨달았다.
그러니까 정렬을 하고, 새로 들어오는 것에 대해 계산만 해주면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <vector>
#include <string>
#include <functional>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <math.h>
using namespace std;
int dx[4] ={-1,1,0,0};
int dy[4]={0,0,1,-1};
bool compare(pair<int,int> a, pair<int,int> b){
if(a.first<b.first)return 1;
else if(a.first==b.first){
if(a.second<b.second)return 1;
else return 0;
}
else return 0;
}
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c;
int n, m, t;
char c1, c2, c3;
cin >> n;
vector<pair<int,int>> v;
long long ans=0;
for(int i=0;i<n;i++){
cin >> a >> b;
v.push_back({a,b});
}
sort(v.begin(), v.end(), compare);
// 밑변 b-a , 높이 b-a*2
ans += (v[0].second-v[0].first)*(v[0].second-v[0].first);
int c_x=v[0].first, c_y=v[0].second;
for(int i=1;i<n;i++){
if(v[i].first > c_y){
ans += (v[i].second-v[i].first)*(v[i].second-v[i].first);
c_x = v[i].first, c_y=v[i].second;
}
else if(v[i].second > c_y){
ans -= (c_y-v[i].first)*(c_y-v[i].first);
ans += (v[i].second-v[i].first)*(v[i].second-v[i].first);
c_y = v[i].second;
}
else continue;
}
cout << ans;
return 0;
}