Cavli

Mirko는 다락방에서 나무판 하나와 못 \(N\)개를 발견했다. Mirko는 최대한 빨리 못들을 판에 박았다. 판은 좌표평면으로, 못들은 그 위의 점으로 모델링할 수 있다. 어떤 두 못도 x좌표나 y좌표가 같지 않다.

계속 재미있게 놀기 위해 Mirko는 여동생의 고무 머리끈을 훔쳐 모든 못 위에 넓게 걸친 다음 놓았다. 고무줄은 당연히 못들을 둘러싸며 팽팽해졌다.

그 다음 Mirko는 판에 못이 세 개 이상 남아 있는 동안 다음 단계를 반복한다:

1. 머리끈이 둘러싼 도형의 넓이를 적는다.
2. 판에서 가장 왼쪽, 가장 오른쪽, 가장 위쪽 또는 가장 아래쪽 못을 고른다.
3. 고른 못을 판에서 뽑는다. 고무줄은 남은 못들을 둘러싸며 다시 팽팽해진다.

각 반복의 2단계에서 Mirko가 고르는 못을 알고 있을 때, 각 반복의 1단계에서 적히는 수들을 계산하는 프로그램을 작성하시오.

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

다음 \(N\)개의 줄에는 공백으로 구분된 두 정수, 못의 좌표가 주어진다. 모든 좌표는 \(1\) 이상 \(1\,000\,000\,000\) 이하이다. x좌표나 y좌표가 같은 두 못은 없다.

다음 줄에 L, R, U, D 중 하나인 문자 \(N-2\)개가 주어진다. 문자는 Mirko가 순서대로 고른 못을 나타낸다:

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

\(N-2\)개의 수를 한 줄에 하나씩 출력한다. Mirko가 적은 넓이를 순서대로 출력하는 것이다. 수는 소수점 아래 한 자리까지 출력한다.

채점: 전체 점수의 \(50\%\)에 해당하는 테스트 케이스에서는 \(N\)이 \(1000\)보다 작다.

riseoj 작성

출처 COCI 2008/2009 Contest 2