Voronoi diagrams P67490


Statement
 

pdf   zip

html

Given n two-dimensional points p1, …, pn, the plane can be decomposed into n regions, each one with the places that are closer to some of the points pi. 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 pi 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++