Time limit per test: 1
Memory limit: 65536
In the game 'Heroes of keyboard and mouse' there are some cities at the plane; each city is situated in a point. The player can build some new cities. All the cities are surrounded by a polygonal wall of minimal length. When a city is built, the wall may be rebuilt to include it. Your task is to determine the area inside the wall each time a new city is built. Of course, the cities are in distinct points.
The game starts with three cities with coordinates (x1
) and (x3
), which are given in the first line of the input. The initial area inside the wall is non-negative. The second line of the input contains single integer N
≤ 100000), being the number of cities to be built. Each of the next N
lines contains the coordinates of a city to be built. All the coordinates are integer and do not exceed 108
by absolute value.
-th line of the output (1≤ K
) must contain an integer, being the doubled area inside the wall after building K
first cities (as listed in the input, not including the first three).
1 0 0 3 3 2
Novosibirsk SU Contest #2, by Novosibirsk Team #1