Fludtown

Time limit2sMemory limit512 MB

Summary

Count the corners of the region inside the square town where the Fenster house is closest.

Level: Medium7 of 10
Topics: Geometry, Math
Solved: No attempts yet

Problem

Fludtown is a square township in Rainee county, one kilometer on each side. The houses are scattered around the township at random, but ownership follows one simple rule: the land at any point in Fludtown belongs to the house whose straight-line distance to that point is shortest. No two houses stand on the same spot.

Last week the Fenster family moved into one of the houses. Mr. Fenster had the property agent drive markers into the edges of his land so that he could build a fence around the house. Yesterday a heavy rainstorm hit Fludtown and washed every marker away. He does still have the town map, which shows where the Fenster house and the other properties are.

Mr. Fenster is going to buy fencing material from the depot outside town. Work out how many fenceposts he needs to buy. A fencepost goes only where the fence changes direction. If his property reaches the border of Fludtown, count the posts needed along the border as well. Some houses have no effect at all on the number of fenceposts.

Input

The location of a Fludtown house is given by its $(x, y)$ coordinates. The origin $(0, 0)$ of the coordinate system sits at the south-west corner of Fludtown, the $x$ axis runs from west to east, the $y$ axis runs from south to north, and one coordinate unit is one meter.

Let $n$ ( $1 \le n \le 10$ ) be the number of houses in Fludtown. The input has $n + 1$ lines. The first line contains the integer $n$ . Each of the next $n$ lines contains two integers $x$ and $y$ separated by a space, the coordinates of one house. The Fenster family house comes before the rest, that is, on the second line. Every house lies inside the square township of area 1 km² or on its edge, so $0 \le x \le 1000$ and $0 \le y \le 1000$ .

Output

Print one integer, the number of fenceposts required to build the fence around the Fenster property.

Hint

The perpendicular bisector of the segment joining $(x_0, y_0)$ and $(x_1, y_1)$ is the line

$(y_1 - y_0)\left(y - \frac{y_0 + y_1}{2}\right) + (x_1 - x_0)\left(x - \frac{x_0 + x_1}{2}\right) = 0$

If the lines $ax + by + c = 0$ and $dx + ey + f = 0$ meet, they meet at

$\left(\frac{bf - ce}{ae - bd}, \frac{cd - af}{ae - bd}\right)$

Examples2

Example 1
Input
```
2
500 500
700 700
```
Expected output
```
5
```
Example 2
Input
```
3
700 700
500 500
200 200
```
Expected output
```
3
```