시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 21 8 6 46.154%

문제

상근이의 방의 한쪽 벽에는 못이 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

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

예제 출력 1

34.0
24.0
16.5
14.0
9.5
5.0

힌트

W3sicHJvYmxlbV9pZCI6IjI5NjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjYmRcdWFjZmMgXHViYWJiIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHViYzI5XHVjNzU4IFx1ZDU1Y1x1Y2FiZCBcdWJjYmRcdWM1ZDBcdWIyOTQgXHViYWJiXHVjNzc0IE5cdWFjMWMgXHViYzE1XHVkNjAwIFx1Yzc4OFx1YjJlNC4gXHVjNTQ0XHVjZTY4XHVjNWQwIFx1Yzc3Y1x1Y2MwZCBcdWM3N2NcdWM1YjRcdWIwOThcdWMxMWMgXHVjNzc0IFx1YmNiZFx1Yzc0NCBcdWJjMTRcdWI3N2NcdWJjZjRcdWJhNzAgXHVkNTU4XHViOGU4XHViOTdjIFx1YzViNFx1YjViYlx1YWM4YyBcdWMwYjQgXHVhYzgzXHVjNzc4XHVhYzAwXHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU1OFx1YjM1OCBcdWM5MTFcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yzc3NCBcdWJjYmRcdWM3NDAgMlx1Y2MyOFx1YzZkMCBcdWQzYzlcdWJhNzRcdWM3NzRcdWFjZTAsIFx1YmFiYlx1Yzc0MCBcdWFkZjggXHVkM2M5XHViYTc0IFx1YzcwNFx1Yzc1OCBcdWM4MTBcdWFjZmMgXHVhYzE5XHViMmU0XHViMjk0IFx1YzBkZFx1YWMwMVx1Yzc0NCBcdWQ1ODhcdWIyZTQuIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViNDUwIFx1YmFiYlx1Yzc0MCBcdWFjMTlcdWM3NDAgeFx1Yzg4Y1x1ZDQ1Y1x1YjA5OCB5XHVjODhjXHVkNDVjXHViOTdjIFx1YWMxNlx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1Y2U2OCBcdWJjMTRcdWIyZTVcdWM1ZDAgXHVhY2UwXHViYjM0XHVjOTA0XHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWI1YThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNWM3XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhY2UwXHViYjM0XHVjOTA0IFx1YzU0OFx1YzVkMCBcdWJhYThcdWI0ZTAgXHViYWJiXHVjNzc0IFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWJhYmJcdWM1ZDAgXHVhY2UwXHViYjM0XHVjOTA0XHVjNzQ0IFx1YWM3OFx1YzViNCBcdWIxOTNcdWM1NThcdWIyZTQuIFx1Yzc3NCBcdWFjZTBcdWJiMzRcdWM5MDRcdWM3NDAgXHViOWU0XHVjNmIwIFx1YmU0NFx1YzJmYyBcdWFjZTBcdWJiMzRcdWM5MDRcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YjA0YVx1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWJjYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFiYlx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjMTM4IFx1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NzggXHViM2Q5XHVjNTQ4XHVjNWQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVhY2ZjXHVjODE1XHVjNzQ0IFx1YWM3MFx1Y2NkMCBcdWJjYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFiYlx1Yzc0NCBcdWJlN2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1YWNlMFx1YmIzNFx1YzkwNFx1Yzc3NCBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YmE3NFx1YzgwMVx1Yzc0NCBcdWM4MDFcdWIyOTRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQsIFx1YzYyNFx1Yjk3OFx1Y2FiZCwgXHVjNzA0LCBcdWM1NDRcdWI3OThcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFiYiBcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1YWNlMFx1Yjk3OFx1YjJlNC48XC9saT5cclxuXHQ8bGk+Mlx1YmM4OFx1YzVkMFx1YzExYyBcdWFjZTBcdWI5NzggXHViYWJiXHVjNzQ0IFx1YmNiZFx1YzVkMFx1YzExYyBcdWM4MWNcdWFjNzBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjdmYyBcdWFjZTBcdWJiMzRcdWM5MDRcdWM3NDAgXHViMGE4XHVjNzQwIFx1YmFiYlx1Yzc0NCBcdWJhYThcdWI0NTAgXHVhYzEwXHVjMmY4XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgMlx1YmM4OCBcdWIyZThcdWFjYzRcdWM1ZDBcdWMxMWMgXHVhY2UwXHViOTc4IFx1YmFiYlx1Yzc3NCBcdWM1YjRcdWI1YTQgXHViYWJiXHVjNzc4XHVjOWMwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIDFcdWJjODggXHViMmU4XHVhY2M0XHVjNWQwXHVjMTFjIFx1YzgwMVx1YjI5NCBcdWJhNzRcdWM4MDFcdWM3NDQgXHViYWE4XHViNDUwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJhYmJcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMyAmbGU7IE4gJmxlOyAzMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYWJiXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWM4OGNcdWQ0NWNcdWIyOTQgMVx1YWNmYyAxLDAwMCwwMDAsMDAwIFx1YzBhY1x1Yzc3NFx1Yzc3NFx1YmE3MCwgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWI0NTAgXHViYWJiXHVjNzc0IFx1YWMxOVx1Yzc0MCB4XHVjODhjXHVkNDVjXHViMDk4IHlcdWM4OGNcdWQ0NWNcdWI5N2MgXHVhYzE2XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgJiMzOTtMJiMzOTssICYjMzk7UiYjMzk7LCYjMzk7IFUmIzM5OywgJiMzOTtEJiMzOTtcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IE4tMlx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCAyXHViYzg4XHViMmU4XHVhY2M0XHVjNWQwXHVjMTFjIFx1YWNlMFx1Yjk3OCBcdWJhYmJcdWM3NTggXHVjODE1XHViY2Y0XHVjNzc0XHViYTcwLCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1Yzc1OFx1YmJmOFx1Yjk3YyBcdWFjMTZcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+JiMzOTtMJiMzOTs6IFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQgXHViYWJiIChcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIHhcdWM4OGNcdWQ0NWMpPFwvbGk+XHJcblx0PGxpPiYjMzk7UiYjMzk7OiBcdWFjMDBcdWM3YTUgXHVjNjI0XHViOTc4XHVjYWJkIFx1YmFiYiAoXHVhYzAwXHVjN2E1IFx1ZDA3MCB4XHVjODhjXHVkNDVjKTxcL2xpPlxyXG5cdDxsaT4mIzM5O1UmIzM5OzogXHVhYzAwXHVjN2E1IFx1YzcwNFx1Y2FiZCBcdWJhYmIgKFx1YWMwMFx1YzdhNSBcdWQwNzAgeVx1Yzg4Y1x1ZDQ1Yyk8XC9saT5cclxuXHQ8bGk+JiMzOTtEJiMzOTs6IFx1YWMwMFx1YzdhNSBcdWM1NDRcdWI3OThcdWNhYmQgXHViYWJiIChcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIHlcdWM4OGNcdWQ0NWMpPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgMVx1YmM4OCBcdWIyZThcdWFjYzRcdWM1ZDBcdWMxMWMgXHVhZDZjXHVkNTU4XHViMjk0IFx1YmE3NFx1YzgwMVx1Yzc0NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNkOWNcdWI4MjVcdWM3NDAgXHVjMThjXHVjMjE4XHVjODEwIFx1Y2NhYlx1YzlmOCBcdWM3OTBcdWI5YWNcdWFlNGNcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL25haWwucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NDEycHg7IHdpZHRoOjYyNHB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyOTY0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ0FWTEkiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGZvdW5kIGEgd29vZGVuIGJvYXJkIGFuZCBOIG5haWxzIGluIGhpcyBhdHRpYy4gTWlya28gaGFtbWVyZWQgdGhlIG5haWxzIGludG8gdGhlIGJvYXJkIGFzIGZhc3QgYXMgcG9zc2libGUuIFRoZSBib2FyZCBjYW4gYmUgbW9kZWxlZCBieSBhIGNvb3JkaW5hdGUgcGxhbmUgYW5kIHRoZSBuYWlscyBhcyBwb2ludHMgaW4gaXQuIE5vIHR3byBuYWlscyBoYXZlIHRoZSBzYW1lIHggb3IgdGhlIHNhbWUgeSBjb29yZGluYXRlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiBvcmRlciB0byBrZWVwIGhhdmluZyBmdW4sIE1pcmtvIHN0b2xlIGhpcyBzaXN0ZXImIzM5O3MgZWxhc3RpYyBoYWlyIGJhbmQsIHNwcmVhZCBpdCBvdmVyIGFsbCBuYWlscyBhbmQgdGhlbiBsZXQgZ28uIFRoZSBlbGFzdGljLCBuYXR1cmFsbHksIHRpZ2h0ZW5lZCBhcm91bmQgdGhlIG5haWxzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5NaXJrbyB0aGVuIHJlcGVhdHMgdGhlc2Ugc3RlcHMgd2hpbGUgdGhlcmUgYXJlIGF0IGxlYXN0IHRocmVlIG5haWxzIGluIHRoZSBib2FyZDombmJzcDs8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5Xcml0ZSBkb3duIHRoZSBhcmVhIG9mIHRoZSBzaGFwZSBlbmNsb3NlZCBieSB0aGUgaGFpciBiYW5kLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5QaWNrcyB0aGUgbGVmdG1vc3QsIHJpZ2h0bW9zdCwgdG9wbW9zdCBvciBib3R0b21tb3N0IG5haWwgaW4gdGhlIGJvYXJkLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5SZW1vdmUgdGhlIGNob3NlbiBuYWlsIGZyb20gdGhlIGJvYXJkOyB0aGUgZWxhc3RpYyB0aWdodGVucyBhZ2FpbiBhcm91bmQgdGhlIHJlbWFpbmluZyBuYWlscy4mbmJzcDs8XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzIHRoZSBudW1iZXJzIHdyaXR0ZW4gaW4gc3RlcCAxIG9mIGVhY2ggaXRlcmF0aW9uLCBpZiB3ZSBrbm93IHRoZSBuYWlsIE1pcmtvIHBpY2tzIGluIHN0ZXAgMiBvZiBlYWNoIGl0ZXJhdGlvbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBpbnRlZ2VyIE4gKDMgJmxlOyBOICZsZTsgMzAwMDAwKSwgdGhlIG51bWJlciBvZiBuYWlscy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzIHNlcGFyYXRlZCBieSBhIHNwYWNlLCB0aGUgY29vcmRpbmF0ZXMgb2YgYSBuYWlsLiBBbGwgY29vcmRpbmF0ZXMgd2lsbCBiZSBiZXR3ZWVuIDEgYW5kIDEwMDAwMDAwMDAuIE5vIHR3byBuYWlscyB3aWxsIHNoYXJlIHRoZSBzYW1lIHggb3IgeSBjb29yZGluYXRlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBsaW5lIGNvbnRhaW5zIE4tMiBsZXR0ZXJzICYjMzk7TCYjMzk7LCAmIzM5O1ImIzM5OywgJiMzOTtVJiMzOTsgb3IgJiMzOTtEJiMzOTsuIFRoZSBsZXR0ZXJzIHJlcHJlc2VudCB0aGUgbmFpbHMgTWlya28gcGlja2VkIGluIG9yZGVyOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiYjMzk7TCYjMzk7IGZvciB0aGUgbGVmdG1vc3QgbmFpbCAoc21hbGxlc3QgeCBjb29yZGluYXRlKSwmbmJzcDs8XC9saT5cclxuXHQ8bGk+JiMzOTtSJiMzOTsgZm9yIHRoZSByaWdodG1vc3QgbmFpbCAobGFyZ2VzdCB4IGNvb3JkaW5hdGUpLCZuYnNwOzxcL2xpPlxyXG5cdDxsaT4mIzM5O1UmIzM5OyBmb3IgdGhlIHRvcG1vc3QgbmFpbCAobGFyZ2VzdCB5IGNvb3JkaW5hdGUpLCZuYnNwOzxcL2xpPlxyXG5cdDxsaT4mIzM5O0QmIzM5OyBmb3IgdGhlIGJvdHRvbW1vc3QgbmFpbCAoc21hbGxlc3QgeSBjb29yZGluYXRlKS48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBOLTIgbnVtYmVycywgZWFjaCBvbiBhIHNlcGFyYXRlIGxpbmUuIFRoZSBudW1iZXJzIGFyZSwgaW4gb3JkZXIsIHRoZSBhcmVhcyB0aGF0IE1pcmtvIHdyb3RlIGRvd24uIE91dHB1dCBudW1iZXJzIHdpdGggb25lIGRpZ2l0IGFmdGVyIHRoZSBkZWNpbWFsIHBvaW50LjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL25haWwucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NDEycHg7IG9wYWNpdHk6MC45OyB3aWR0aDo2MjRweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d