277. Heroes
Time limit per test: 1 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard
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.
Input
The game starts with three cities with coordinates (
x1,
y1), (
x2,
y2) and (
x3,
y3), 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 (1≤
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 10
8 by absolute value.
Output
The
K-th line of the output (1≤
K≤
N) 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).
Example(s)
sample input | sample output |
1 0 0 3 3 2
5
1 2
2 1
3 0
2 3
0 1
|
8
8
12
14
16
|
Novosibirsk SU Contest #2, by Novosibirsk Team #1