COCI 2008/2009, Contest #2
Mirko found a wooden board and N nails in his attic. Mirko hammered the nails into the board as fast as possible. The board can be modeled by a coordinate plane and the nails as points in it. No two nails have the same x or the same y coordinate.
In order to keep having fun, Mirko stole his sister's elastic hair band, spread it over all nails and then let go. The elastic, naturally, tightened around the nails.
Mirko then repeats these steps while there are at least three nails in the board:
- Write down the area of the shape enclosed by the hair band.
- Picks the leftmost, rightmost, topmost or bottommost nail in the board.
- Remove the chosen nail from the board; the elastic tightens again around the remaining nails.
Write a program that calculates the numbers written in step 1 of each iteration, if we know the nail Mirko picks in step 2 of each iteration.
The first line contains the integer N (3 ≤ N ≤ 300,000), the number of nails.
Each of the following N lines contains two integers separated by a space, the coordinates of a nail. All coordinates will be between 1 and 1 000 000 000. No two nails will share the same x or y coordinate.
The next line contains N-2 letters 'L', 'R', 'U' or 'D'. The letters represent the nails Mirko picked in order:
- 'L' for the leftmost nail (smallest x coordinate),
- 'R' for the rightmost nail (largest x coordinate),
- 'U' for the topmost nail (largest y coordinate),
- 'D' for the bottommost nail (smallest y coordinate).
OutputOutput N-2 numbers, each on a separate line. The numbers are, in order, the areas that Mirko wrote down. Output numbers with one digit after the decimal point.
ScoringIn test cases worth 50% points, N will be less than 1000.
5 1 4 2 2 4 1 3 5 5 3 LUR
9.0 6.5 2.5
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
The images below illustrate the state before each of the 6 steps in the second example.
Point Value: 40 (partial)
Time Limit: 3.00s
Memory Limit: 32M
Added: Nov 22, 2008
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3