A8162 | Save the City!

In the town of Aalam-Aara (meaning the Light of the Earth), previously there was no crime, no criminals but as the time progressed, sins started creeping into the hearts of once righteous people. Seeking solution to the problem, some of the elders found that as long as the corrupted part of population was kept away from the uncorrupted part, the crimes could be stopped. So, they are trying to set up a compound where they can keep the corrupted people. To ensure that the criminals don't escape the compound, a watchtower needs to be set up, so that they can be watched.

Since the people of Aalam-Aara aren't very rich, they met up with a merchant from some rich town who agreed to sell them a land-plot which has already a straight line fence $AB$ along which a few points are set up where they can put up a watchtower. Your task is to help them find out the number of points on that fence where the tower can be put up, so that all the criminals can be watched from there. Only one watchtower can be set up. A criminal is watchable from the watchtower if the line of visibility from the watchtower to him doesn't cross the plot-edges at any point between him and the tower i.e. as shown in figure 1 below, points $X$ , $Y$ , $C$ and $A$ are visible from point $B$ but the points $E$ and $D$ are not.

 Figure 1  Figure 2 Assume that the land plot is in the shape of a polygon and coordinate axes have been setup such that the fence $AB$ is parallel to $x$ -axis and the points where the watchtower can be set up are the integer points on the line. For example, in given figure 2, watchtower can be setup on any of five integer points on $AB$ i.e. $(4,8)$ , $(5,8)$ , $(6,8)$ , $(7,8)$ or $(8,8)$ . You can assume that no three consecutive points are collinear and all the corner points other than $A$ and $B$ , lie towards same side of fence $AB$ . The given polygon doesn't contain self-intersections.

The first line of the test case will consist of the number of vertices $n$ ( $3<=n<=1000$ ).

Next $n$ lines will contain the coordinates of the vertices in the clockwise order of the polygon. On the $i$ -th line are integers $x_{i}$ and $y_{i}$ ( $0<=x_{i},y_{i}<=10^{6}$ ) separated by a space.

The endpoints of the fence $AB$ are the first two points, $(x_{1},y_{1})$ and $(x_{2},y_{2})$ .

Output consists of a single line containing the number of points where the watchtower can be set up.