시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB63211136.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번 단계에서 구하는 면적을 순서대로 한 줄에 하나씩 출력한다. 출력은 소수점 첫째 자리까지 출력한다.

예제 입력 1

5
1 4
2 2
4 1
3 5
5 3
LUR

예제 출력 1

9.0
6.5
2.5

예제 입력 2

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

예제 출력 2

34.0
24.0
16.5
14.0
9.5
5.0

W3sicHJvYmxlbV9pZCI6IjI5NjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjYmRcdWFjZmMgXHViYWJiIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHViYzI5XHVjNzU4IFx1ZDU1Y1x1Y2FiZCBcdWJjYmRcdWM1ZDBcdWIyOTQgXHViYWJiXHVjNzc0IE5cdWFjMWMgXHViYzE1XHVkNjAwIFx1Yzc4OFx1YjJlNC4gXHVjNTQ0XHVjZTY4XHVjNWQwIFx1Yzc3Y1x1Y2MwZCBcdWM3N2NcdWM1YjRcdWIwOThcdWMxMWMgXHVjNzc0IFx1YmNiZFx1Yzc0NCBcdWJjMTRcdWI3N2NcdWJjZjRcdWJhNzAgXHVkNTU4XHViOGU4XHViOTdjIFx1YzViNFx1YjViYlx1YWM4YyBcdWMwYjQgXHVhYzgzXHVjNzc4XHVhYzAwXHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU1OFx1YjM1OCBcdWM5MTFcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yzc3NCBcdWJjYmRcdWM3NDAgMlx1Y2MyOFx1YzZkMCBcdWQzYzlcdWJhNzRcdWM3NzRcdWFjZTAsIFx1YmFiYlx1Yzc0MCBcdWFkZjggXHVkM2M5XHViYTc0IFx1YzcwNFx1Yzc1OCBcdWM4MTBcdWFjZmMgXHVhYzE5XHViMmU0XHViMjk0IFx1YzBkZFx1YWMwMVx1Yzc0NCBcdWQ1ODhcdWIyZTQuIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViNDUwIFx1YmFiYlx1Yzc0MCBcdWFjMTlcdWM3NDAgeFx1Yzg4Y1x1ZDQ1Y1x1YjA5OCB5XHVjODhjXHVkNDVjXHViOTdjIFx1YWMxNlx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1Y2U2OCBcdWJjMTRcdWIyZTVcdWM1ZDAgXHVhY2UwXHViYjM0XHVjOTA0XHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWI1YThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNWM4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhY2UwXHViYjM0XHVjOTA0IFx1YzU0OFx1YzVkMCBcdWJhYThcdWI0ZTAgXHViYWJiXHVjNzc0IFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWJhYmJcdWM1ZDAgXHVhY2UwXHViYjM0XHVjOTA0XHVjNzQ0IFx1YWM3OFx1YzViNCBcdWIxOTNcdWM1NThcdWIyZTQuIFx1Yzc3NCBcdWFjZTBcdWJiMzRcdWM5MDRcdWM3NDAgXHViOWU0XHVjNmIwIFx1YmU0NFx1YzJmYyBcdWFjZTBcdWJiMzRcdWM5MDRcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YjA0YVx1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWJjYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFiYlx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjMTM4IFx1YWMxY1x1YmNmNFx1YjJlNCBcdWM4MDFcdWM1YjRcdWM5YzggXHViNTRjXHVhZTRjXHVjOWMwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVhY2ZjXHVjODE1XHVjNzQ0IFx1YWM3MFx1Y2NkMCBcdWJjYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFiYlx1Yzc0NCBcdWJlN2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1YWNlMFx1YmIzNFx1YzkwNFx1Yzc3NCBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YmE3NFx1YzgwMVx1Yzc0NCBcdWM4MDFcdWIyOTRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQsIFx1YzYyNFx1Yjk3OFx1Y2FiZCwgXHVjNzA0LCBcdWM1NDRcdWI3OThcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFiYiBcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1YWNlMFx1Yjk3OFx1YjJlNC48XC9saT5cclxuXHQ8bGk+Mlx1YmM4OFx1YzVkMFx1YzExYyBcdWFjZTBcdWI5NzggXHViYWJiXHVjNzQ0IFx1YmNiZFx1YzVkMFx1YzExYyBcdWM4MWNcdWFjNzBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjdmYyBcdWFjZTBcdWJiMzRcdWM5MDRcdWM3NDAgXHViMGE4XHVjNzQwIFx1YmFiYlx1Yzc0NCBcdWJhYThcdWI0NTAgXHVhYzEwXHVjMmY4XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgMlx1YmM4OCBcdWIyZThcdWFjYzRcdWM1ZDBcdWMxMWMgXHVhY2UwXHViOTc4IFx1YmFiYlx1Yzc3NCBcdWM1YjRcdWI1YTQgXHViYWJiXHVjNzc4XHVjOWMwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIDFcdWJjODggXHViMmU4XHVhY2M0XHVjNWQwXHVjMTFjIFx1YzgwMVx1YjI5NCBcdWJhNzRcdWM4MDFcdWM3NDQgXHViYWE4XHViNDUwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJhYmJcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMyAmbGU7IE4gJmxlOyAzMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYWJiXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWM4OGNcdWQ0NWNcdWIyOTQgMVx1YWNmYyAxLDAwMCwwMDAsMDAwIFx1YzBhY1x1Yzc3NFx1Yzc3NFx1YmE3MCwgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWI0NTAgXHViYWJiXHVjNzc0IFx1YWMxOVx1Yzc0MCB4XHVjODhjXHVkNDVjXHViMDk4IHlcdWM4OGNcdWQ0NWNcdWI5N2MgXHVhYzE2XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgJiMzOTtMJiMzOTssICYjMzk7UiYjMzk7LCYjMzk7IFUmIzM5OywgJiMzOTtEJiMzOTtcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IE4tMlx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCAyXHViYzg4XHViMmU4XHVhY2M0XHVjNWQwXHVjMTFjIFx1YWNlMFx1Yjk3OCBcdWJhYmJcdWM3NTggXHVjODE1XHViY2Y0XHVjNzc0XHViYTcwLCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1Yzc1OFx1YmJmOFx1Yjk3YyBcdWFjMTZcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+JiMzOTtMJiMzOTs6IFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQgXHViYWJiIChcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIHhcdWM4OGNcdWQ0NWMpPFwvbGk+XHJcblx0PGxpPiYjMzk7UiYjMzk7OiBcdWFjMDBcdWM3YTUgXHVjNjI0XHViOTc4XHVjYWJkIFx1YmFiYiAoXHVhYzAwXHVjN2E1IFx1ZDA3MCB4XHVjODhjXHVkNDVjKTxcL2xpPlxyXG5cdDxsaT4mIzM5O1UmIzM5OzogXHVhYzAwXHVjN2E1IFx1YzcwNFx1Y2FiZCBcdWJhYmIgKFx1YWMwMFx1YzdhNSBcdWQwNzAgeVx1Yzg4Y1x1ZDQ1Yyk8XC9saT5cclxuXHQ8bGk+JiMzOTtEJiMzOTs6IFx1YWMwMFx1YzdhNSBcdWM1NDRcdWI3OThcdWNhYmQgXHViYWJiIChcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIHlcdWM4OGNcdWQ0NWMpPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgMVx1YmM4OCBcdWIyZThcdWFjYzRcdWM1ZDBcdWMxMWMgXHVhZDZjXHVkNTU4XHViMjk0IFx1YmE3NFx1YzgwMVx1Yzc0NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNkOWNcdWI4MjVcdWM3NDAgXHVjMThjXHVjMjE4XHVjODEwIFx1Y2NhYlx1YzlmOCBcdWM3OTBcdWI5YWNcdWFlNGNcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiA8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJzYW1wbGVfZXhwbGFpbl8yIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9iMWQzMjUzNi0yOWQ4LTQ5ZjYtYTFhYi02MmEzOTRmOWQ2YjRcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDYwNXB4OyBoZWlnaHQ6IDM5OXB4O1wiIFwvPjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjI5NjQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDQVZMSSIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gZm91bmQgYSB3b29kZW4gYm9hcmQgYW5kIE4gbmFpbHMgaW4gaGlzIGF0dGljLiBNaXJrbyBoYW1tZXJlZCB0aGUgbmFpbHMgaW50byB0aGUgYm9hcmQgYXMgZmFzdCBhcyBwb3NzaWJsZS4gVGhlIGJvYXJkIGNhbiBiZSBtb2RlbGVkIGJ5IGEgY29vcmRpbmF0ZSBwbGFuZSBhbmQgdGhlIG5haWxzIGFzIHBvaW50cyBpbiBpdC4gTm8gdHdvIG5haWxzIGhhdmUgdGhlIHNhbWUgeCBvciB0aGUgc2FtZSB5IGNvb3JkaW5hdGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluIG9yZGVyIHRvIGtlZXAgaGF2aW5nIGZ1biwgTWlya28gc3RvbGUgaGlzIHNpc3RlciYjMzk7cyBlbGFzdGljIGhhaXIgYmFuZCwgc3ByZWFkIGl0IG92ZXIgYWxsIG5haWxzIGFuZCB0aGVuIGxldCBnby4gVGhlIGVsYXN0aWMsIG5hdHVyYWxseSwgdGlnaHRlbmVkIGFyb3VuZCB0aGUgbmFpbHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk1pcmtvIHRoZW4gcmVwZWF0cyB0aGVzZSBzdGVwcyB3aGlsZSB0aGVyZSBhcmUgYXQgbGVhc3QgdGhyZWUgbmFpbHMgaW4gdGhlIGJvYXJkOiZuYnNwOzxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPldyaXRlIGRvd24gdGhlIGFyZWEgb2YgdGhlIHNoYXBlIGVuY2xvc2VkIGJ5IHRoZSBoYWlyIGJhbmQuJm5ic3A7PFwvbGk+XHJcblx0PGxpPlBpY2tzIHRoZSBsZWZ0bW9zdCwgcmlnaHRtb3N0LCB0b3Btb3N0IG9yIGJvdHRvbW1vc3QgbmFpbCBpbiB0aGUgYm9hcmQuJm5ic3A7PFwvbGk+XHJcblx0PGxpPlJlbW92ZSB0aGUgY2hvc2VuIG5haWwgZnJvbSB0aGUgYm9hcmQ7IHRoZSBlbGFzdGljIHRpZ2h0ZW5zIGFnYWluIGFyb3VuZCB0aGUgcmVtYWluaW5nIG5haWxzLiZuYnNwOzxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGNhbGN1bGF0ZXMgdGhlIG51bWJlcnMgd3JpdHRlbiBpbiBzdGVwIDEgb2YgZWFjaCBpdGVyYXRpb24sIGlmIHdlIGtub3cgdGhlIG5haWwgTWlya28gcGlja3MgaW4gc3RlcCAyIG9mIGVhY2ggaXRlcmF0aW9uLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIGludGVnZXIgTiAoMyAmbGU7IE4gJmxlOyAzMDAwMDApLCB0aGUgbnVtYmVyIG9mIG5haWxzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IGEgc3BhY2UsIHRoZSBjb29yZGluYXRlcyBvZiBhIG5haWwuIEFsbCBjb29yZGluYXRlcyB3aWxsIGJlIGJldHdlZW4gMSBhbmQgMTAwMDAwMDAwMC4gTm8gdHdvIG5haWxzIHdpbGwgc2hhcmUgdGhlIHNhbWUgeCBvciB5IGNvb3JkaW5hdGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmUgY29udGFpbnMgTi0yIGxldHRlcnMgJiMzOTtMJiMzOTssICYjMzk7UiYjMzk7LCAmIzM5O1UmIzM5OyBvciAmIzM5O0QmIzM5Oy4gVGhlIGxldHRlcnMgcmVwcmVzZW50IHRoZSBuYWlscyBNaXJrbyBwaWNrZWQgaW4gb3JkZXI6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+JiMzOTtMJiMzOTsgZm9yIHRoZSBsZWZ0bW9zdCBuYWlsIChzbWFsbGVzdCB4IGNvb3JkaW5hdGUpLCZuYnNwOzxcL2xpPlxyXG5cdDxsaT4mIzM5O1ImIzM5OyBmb3IgdGhlIHJpZ2h0bW9zdCBuYWlsIChsYXJnZXN0IHggY29vcmRpbmF0ZSksJm5ic3A7PFwvbGk+XHJcblx0PGxpPiYjMzk7VSYjMzk7IGZvciB0aGUgdG9wbW9zdCBuYWlsIChsYXJnZXN0IHkgY29vcmRpbmF0ZSksJm5ic3A7PFwvbGk+XHJcblx0PGxpPiYjMzk7RCYjMzk7IGZvciB0aGUgYm90dG9tbW9zdCBuYWlsIChzbWFsbGVzdCB5IGNvb3JkaW5hdGUpLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IE4tMiBudW1iZXJzLCBlYWNoIG9uIGEgc2VwYXJhdGUgbGluZS4gVGhlIG51bWJlcnMgYXJlLCBpbiBvcmRlciwgdGhlIGFyZWFzIHRoYXQgTWlya28gd3JvdGUgZG93bi4gT3V0cHV0IG51bWJlcnMgd2l0aCBvbmUgZGlnaXQgYWZ0ZXIgdGhlIGRlY2ltYWwgcG9pbnQuPFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBpbWFnZXMgYmVsb3cgaWxsdXN0cmF0ZSB0aGUgc3RhdGUgYmVmb3JlIGVhY2ggb2YgdGhlIDYgc3RlcHMgaW4gdGhlIHNlY29uZCBleGFtcGxlLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2IxZDMyNTM2LTI5ZDgtNDlmNi1hMWFiLTYyYTM5NGY5ZDZiNFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNjA1cHg7IGhlaWdodDogMzk5cHg7XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2008/2009 > Contest #2 6번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013