Given *n* two-dimensional points *p*_{1}, …, *p*_{n},
the plane can be decomposed into *n* regions,
each one with the places that are closer to some of the points *p*_{i}.
This is called the Voronoi diagram of the given set of points.
For instance, the points
(−30,25), (−20,−5), (−20,15), (−10,15), (−10,25) and (20,15)
define the following regions
(Cartesian coordinates in blue, points in green,
and edges of the regions in black):

unit=0.08cm
(100,80)

linewidth=0.5pt linestyle=dotted linecolor=blue

(70,00)(70,75) (70,75)(68.5,71) (70,75)(71.5,71) (00,25)(100,25) (100,25)(96,23.5) (100,25)(96,26.5)

linestyle=dashed linecolor=black

(00,20)(15,25) (80,60)(85,75) (50,65)(50,75) (80,10)(85,00)

linestyle=solid

(30,30)(55,30) (55,30)(55,45) (30,30)(50,50) (15,25)(30,30) (75,20)(75,45) (50,50)(50,65) (55,45)(75,45) (50,50)(55,45) (55,30)(75,20) (75,45)(80,60) (75,20)(80,10)

linewidth=4pt linecolor=green

(40,50)0.5 (50,40)0.5 (50,20)0.5 (60,40)0.5 (60,50)0.5 (90,40)0.5

linecolor=red

(30,40)0.5 (90,25)0.5

linewidth=0.5pt linestyle=dashed

(30,40)(90,25)

Note that each region is convex. The edges correspond to places equidistant to the two nearest points. The vertices are the places equidistant to three (or more) points.

Given two arbitrary points *a* and *b* in the plane,
the segment that connects them crosses several edges of the Voronoi diagram.
How many?
For instance,
the segment that connects (−40,15)
and (20,0)—in red in the picture—crosses 3 edges.

**Input**

Input consists of several cases.
Each case begins with *n*,
followed by the coordinates of *p*_{i} for every *i*,
followed by the coordinates of *a* and *b*.
The coordinates are real numbers
with at most two digits after the decimal point.
The *n* + 2 given points and the vertices of the diagram are different
and not closer than 0.01 units.
The segment does not overlap any edge
and is not closer than 0.01 units to any vertex.
Assume 1 ≤ *n* ≤ 100.

**Output**

For every case, print the number of edges
crossed by the segment that connects *a* and *b*.

Public test cases

**Input**

6 -30 25 -20 -5 -20 15 -10 15 -10 25 20 15 -40 15 20 0 1 0 0 4.21 0 0 2.35 2 1 0 0 0 1 1 0 1 2 1 0 0 0 1 1 2 1

**Output**

3 0 1 0

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++