시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB3910847.059%

문제

상근이의 방의 한쪽 벽에는 못이 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+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgMVx1YmM4OCBcdWIyZThcdWFjYzRcdWM1ZDBcdWMxMWMgXHVhZDZjXHVkNTU4XHViMjk0IFx1YmE3NFx1YzgwMVx1Yzc0NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNkOWNcdWI4MjVcdWM3NDAgXHVjMThjXHVjMjE4XHVjODEwIFx1Y2NhYlx1YzlmOCBcdWM3OTBcdWI5YWNcdWFlNGNcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsInNhbXBsZV9leHBsYWluXzIiOiI8cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2IxZDMyNTM2LTI5ZDgtNDlmNi1hMWFiLTYyYTM5NGY5ZDZiNFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNjA1cHg7IGhlaWdodDogMzk5cHg7XCIgXC8+PFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMjk2NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNBVkxJIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBmb3VuZCBhIHdvb2RlbiBib2FyZCBhbmQgTiBuYWlscyBpbiBoaXMgYXR0aWMuIE1pcmtvIGhhbW1lcmVkIHRoZSBuYWlscyBpbnRvIHRoZSBib2FyZCBhcyBmYXN0IGFzIHBvc3NpYmxlLiBUaGUgYm9hcmQgY2FuIGJlIG1vZGVsZWQgYnkgYSBjb29yZGluYXRlIHBsYW5lIGFuZCB0aGUgbmFpbHMgYXMgcG9pbnRzIGluIGl0LiBObyB0d28gbmFpbHMgaGF2ZSB0aGUgc2FtZSB4IG9yIHRoZSBzYW1lIHkgY29vcmRpbmF0ZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SW4gb3JkZXIgdG8ga2VlcCBoYXZpbmcgZnVuLCBNaXJrbyBzdG9sZSBoaXMgc2lzdGVyJiMzOTtzIGVsYXN0aWMgaGFpciBiYW5kLCBzcHJlYWQgaXQgb3ZlciBhbGwgbmFpbHMgYW5kIHRoZW4gbGV0IGdvLiBUaGUgZWxhc3RpYywgbmF0dXJhbGx5LCB0aWdodGVuZWQgYXJvdW5kIHRoZSBuYWlscy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TWlya28gdGhlbiByZXBlYXRzIHRoZXNlIHN0ZXBzIHdoaWxlIHRoZXJlIGFyZSBhdCBsZWFzdCB0aHJlZSBuYWlscyBpbiB0aGUgYm9hcmQ6Jm5ic3A7PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+V3JpdGUgZG93biB0aGUgYXJlYSBvZiB0aGUgc2hhcGUgZW5jbG9zZWQgYnkgdGhlIGhhaXIgYmFuZC4mbmJzcDs8XC9saT5cclxuXHQ8bGk+UGlja3MgdGhlIGxlZnRtb3N0LCByaWdodG1vc3QsIHRvcG1vc3Qgb3IgYm90dG9tbW9zdCBuYWlsIGluIHRoZSBib2FyZC4mbmJzcDs8XC9saT5cclxuXHQ8bGk+UmVtb3ZlIHRoZSBjaG9zZW4gbmFpbCBmcm9tIHRoZSBib2FyZDsgdGhlIGVsYXN0aWMgdGlnaHRlbnMgYWdhaW4gYXJvdW5kIHRoZSByZW1haW5pbmcgbmFpbHMuJm5ic3A7PFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FsY3VsYXRlcyB0aGUgbnVtYmVycyB3cml0dGVuIGluIHN0ZXAgMSBvZiBlYWNoIGl0ZXJhdGlvbiwgaWYgd2Uga25vdyB0aGUgbmFpbCBNaXJrbyBwaWNrcyBpbiBzdGVwIDIgb2YgZWFjaCBpdGVyYXRpb24uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aGUgaW50ZWdlciBOICgzICZsZTsgTiAmbGU7IDMwMDAwMCksIHRoZSBudW1iZXIgb2YgbmFpbHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgYSBzcGFjZSwgdGhlIGNvb3JkaW5hdGVzIG9mIGEgbmFpbC4gQWxsIGNvb3JkaW5hdGVzIHdpbGwgYmUgYmV0d2VlbiAxIGFuZCAxMDAwMDAwMDAwLiBObyB0d28gbmFpbHMgd2lsbCBzaGFyZSB0aGUgc2FtZSB4IG9yIHkgY29vcmRpbmF0ZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgbGluZSBjb250YWlucyBOLTIgbGV0dGVycyAmIzM5O0wmIzM5OywgJiMzOTtSJiMzOTssICYjMzk7VSYjMzk7IG9yICYjMzk7RCYjMzk7LiBUaGUgbGV0dGVycyByZXByZXNlbnQgdGhlIG5haWxzIE1pcmtvIHBpY2tlZCBpbiBvcmRlcjombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4mIzM5O0wmIzM5OyBmb3IgdGhlIGxlZnRtb3N0IG5haWwgKHNtYWxsZXN0IHggY29vcmRpbmF0ZSksJm5ic3A7PFwvbGk+XHJcblx0PGxpPiYjMzk7UiYjMzk7IGZvciB0aGUgcmlnaHRtb3N0IG5haWwgKGxhcmdlc3QgeCBjb29yZGluYXRlKSwmbmJzcDs8XC9saT5cclxuXHQ8bGk+JiMzOTtVJiMzOTsgZm9yIHRoZSB0b3Btb3N0IG5haWwgKGxhcmdlc3QgeSBjb29yZGluYXRlKSwmbmJzcDs8XC9saT5cclxuXHQ8bGk+JiMzOTtEJiMzOTsgZm9yIHRoZSBib3R0b21tb3N0IG5haWwgKHNtYWxsZXN0IHkgY29vcmRpbmF0ZSkuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgTi0yIG51bWJlcnMsIGVhY2ggb24gYSBzZXBhcmF0ZSBsaW5lLiBUaGUgbnVtYmVycyBhcmUsIGluIG9yZGVyLCB0aGUgYXJlYXMgdGhhdCBNaXJrbyB3cm90ZSBkb3duLiBPdXRwdXQgbnVtYmVycyB3aXRoIG9uZSBkaWdpdCBhZnRlciB0aGUgZGVjaW1hbCBwb2ludC48XC9wPlxyXG4iLCJoaW50IjoiPHA+VGhlIGltYWdlcyBiZWxvdyBpbGx1c3RyYXRlIHRoZSBzdGF0ZSBiZWZvcmUgZWFjaCBvZiB0aGUgNiBzdGVwcyBpbiB0aGUgc2Vjb25kIGV4YW1wbGUuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvYjFkMzI1MzYtMjlkOC00OWY2LWExYWItNjJhMzk0ZjlkNmI0XC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA2MDVweDsgaGVpZ2h0OiAzOTlweDtcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

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

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