벽과 못
시간 제한1초메모리 제한128 MB
못들의 집합에서 최좌단, 최우단, 최상단, 최하단 점을 차례로 제거하면서 매 단계마다 남은 점들의 convex hull 넓이를 구하는 문제입니다.
문제
한 벽에 못이 N개 박혀 있다. 벽을 2차원 평면으로 보고, 각 못을 평면 위의 한 점으로 생각하자. 서로 다른 두 못은 같은 x좌표나 같은 y좌표를 갖지 않는다.
고무줄 하나를 모든 못이 안에 들어가도록 걸면, 고무줄은 현재 남아 있는 못들의 볼록 껍질을 이룬다. 못이 세 개보다 적게 남을 때까지 다음 과정을 반복한다.
- 현재 고무줄이 만드는 다각형의 넓이를 기록한다.
- 현재 남아 있는 못 중 가장 왼쪽, 가장 오른쪽, 가장 위쪽, 가장 아래쪽 못 중 하나를 고른다.
- 고른 못을 벽에서 제거한다. 고무줄은 다시 남은 못들을 모두 감싼다.
각 단계에서 어떤 방향의 못을 제거하는지가 주어진다. 매 단계에서 기록되는 넓이를 구하시오.
입력
첫째 줄에 못의 개수 N이 주어진다. (3 <= N <= 300000)
다음 N개 줄에는 못의 좌표 x, y가 주어진다. 모든 좌표는 1 이상 1000000000 이하의 정수이며, 서로 다른 두 못이 같은 x좌표나 같은 y좌표를 갖지 않는다.
마지막 줄에는 길이가 N-2인 문자열이 주어진다. 각 문자는 제거할 못을 뜻한다.
- L: 현재 가장 왼쪽에 있는 못
- R: 현재 가장 오른쪽에 있는 못
- U: 현재 가장 위쪽에 있는 못
- D: 현재 가장 아래쪽에 있는 못
출력
각 단계에서 기록한 넓이를 순서대로 한 줄에 하나씩 출력한다. 넓이는 소수점 첫째 자리까지 출력한다.