beecrowd | 2901

Martian Volleyball

By BR Brazil

Timelimit: 1

Just like on Earth, volleyball is a very popular sport on Mars; the rules there are the same as those of earthly volleyball - teams should not let the ball touch in their part of the court - but there is one important difference: unlike earthly volleyball, the courts are not necessarily rectangular; they can be any polygons as long as their sides are parallel to the coordinate axes. Just like in terrestrial volleyball, polemical throws are those where the ball falls too close to the court line. To avoid arguments, all Martian volleyball games are accompanied by line judges. Their function is to watch the ball as it falls next to one of the lines and tell whether it fell on or off the court. When a judge is in line with several lines of court, he can observe all of them at the same time (in the set of lines under the responsibility of the same judge there may even be lines perpendicular to each other). However, in order to avoid accidents, the Intergalactic Federation of Martian Volleyball decreed the following safety standards:

• the judges should stand still during the game;

• the judges can not stay inside the court, not even on their line. The image below illustrates three possible block formats, showing a minimum allocation of judges for each of them; the court (a) needs four judges, the court (b) needs seven judges, and the court (c) needs six judges.

You should write a program that, given the format of the court, determines the minimum number of line judges necessary for all lines on the court to be accompanied by at least one judge.


The input contains several test cases. The first line of a test case contain an even integerN, which indicates the number of sides of the volleyball court (4 ≤ N ≤ 100). Each one of N following lines contain two integers Xi and Yi, representing the coordinates of one of the vertices of the court (− ≤ Xi , Yi ≤ The coordinates are given in order, so that (Xi, Yi) form a side of the court with (Xi+1, Yi+1), to 1 ≤ i < N, and (XN , YN ) form a side with (X1, Y1). Consecutive court sides are always perpendicular, and the polygon described at the entrance is always a simple polygon. The end of the entry is indicated by N = 0.


For each input test case your program must produce a single line in the output, containing an integer, indicating the least number of line judges required.

Input Sample Output Sample


0 0

9 0

9 18

0 18


0 0

0 1

1 1

1 -1

-2 -1

-2 1

-1 1

-1 0


1 0

2 0

2 1

3 1

3 2

2 2

2 3

1 3

1 2

0 2

0 1

1 1