C++ [BOJ] 백준 2304번 창고 다각형

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

2304번: 창고 다각형

---

SOLUTION

스택을 이용해 푼 문제다.

비가 올 때 물이 고이지 않게 오목한 부분이 없도록 만들기 위해서 왼쪽에서 오른쪽으로 가면서 한번, 오른쪽에서 왼쪽으로 가면서 한번 탐색을 해서 높이가 커지는 것들만 집어넣어 가면서 넓이를 계산했다.

두번의 탐색에서 높이가 가장 큰 것들의 높이는 같을것이고, x좌표가 같다면 1*높이, x좌표가 다르다면 가로*높이를 추가해줬다.

---

코드

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int n;
	cin >> n;
	int ans = 0;
	vector<pair<int, int>>v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i].first >> v[i].second;
	}
	sort(v.begin(), v.end());
	stack<pair<int,int>>s;
	s.push({ v[0].first,v[0].second });
	for (int i = 1; i < n; i++) {
		if (v[i].second > s.top().second) s.push({ v[i].first, v[i].second });
	}
	int x = s.top().first;
	int y = s.top().second;
	while (s.size()>=2) {
		int width = s.top().first;
		s.pop();
		width -= s.top().first;
		int height = s.top().second;
		ans += width * height;
	}
	s.pop();
	//
	s.push({ v[n - 1].first,v[n - 1].second });
	for (int i = n - 2; i >= 0; i--) {
		if (v[i].second > s.top().second) s.push({ v[i].first,v[i].second });
	}
	if (x == s.top().first) ans += s.top().second;
	else ans += (s.top().first - x + 1) * s.top().second;
	while (s.size() >= 2) {
		int width = s.top().first;
		s.pop();
		width -= s.top().first;
		width *= -1;
		int height = s.top().second;
		ans += width * height;
	}
	s.pop();
	cout << ans;
}