시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 16 5 5 41.667%

문제

상근이의 방의 한쪽 벽에는 못이 N개 박혀 있다. 아침에 일찍 일어나서 이 벽을 바라보며 하루를 어떻게 살 것인가를 생각하던 중에 상근이는 이 벽은 2차원 평면이고, 못은 그 평면 위의 점과 같다는 생각을 했다. 서로 다른 두 못은 같은 x좌표나 y좌표를 갖지 않는다.

마침 바닥에 고무줄이 하나 떨어져 있엇다. 상근이는 고무줄 안에 모든 못이 포함되도록 못에 고무줄을 걸어 놓았다. 이 고무줄은 매우 비싼 고무줄이기 때문에 끊어지지 않는다.

상근이는 벽에 있는 못의 개수가 세 개 이상인 동안에 아래와 같은 과정을 거쳐 벽에 있는 못을 빼려고 한다.

  1. 고무줄이 만드는 다각형의 면적을 적는다.
  2. 가장 왼쪽, 오른쪽, 위, 아래에 있는 못 중 하나를 고른다.
  3. 2번에서 고른 못을 벽에서 제거한다. 그럼 고무줄은 남은 못을 모두 감싸게 된다.

상근이가 2번 단계에서 고른 못이 어떤 못인지 주어졌을 때, 1번 단계에서 적는 면적을 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 못의 개수 N이 주어진다. (3 ≤ N ≤ 300,000)

다음 N개 줄에는 못의 좌표가 주어진다. 모든 좌표는 1과 1,000,000,000 사이이며, 서로 다른 두 못이 같은 x좌표나 y좌표를 갖는 경우는 없다.

마지막 줄에는 'L', 'R',' U', 'D'로 이루어진 N-2개의 문자열이 주어진다. 이 문자열은 상근이가 2번단계에서 고른 못의 정보이며, 다음과 같은 의미를 갖는다.

  • 'L': 가장 왼쪽 못 (가장 작은 x좌표)
  • 'R': 가장 오른쪽 못 (가장 큰 x좌표)
  • 'U': 가장 위쪽 못 (가장 큰 y좌표)
  • 'D': 가장 아래쪽 못 (가장 작은 y좌표)

출력

상근이가 1번 단계에서 구하는 면적을 순서대로 한 줄에 하나씩 출력한다. 출력은 소수점 첫째 자리까지 출력한다. 

예제 입력

8
1 6
2 4
3 1
4 2
5 7
6 5
7 9
8 3
URDLUU

예제 출력

34.0
24.0
16.5
14.0
9.5
5.0

힌트