In the 2-dimensional Cartesian coordinate system, we define the Voronoi Diagram of a non-empty set of points SS, as a diagram that divides the plane by the criteria “which point in the set SS is closest in this location?”. More precisely, the Voronoi diagram of a given non-empty point set {P1,P2,⋯,Pn} {P1,P2,⋯,Pn} is a collection of regions: A point KK is included in region ii if and only if d(Pi,K)≤d(Pj,K)d(Pi,K)≤d(Pj,K) holds for all 1≤j≤n1≤j≤n, where d(X,Y)d(X,Y) denotes the Euclidean distance between point XX and YY.
For example, in the picture above, every location over the plane is colored by the closest point with such location. The points which belongs to a single region is colored by a light color indicating a region, and the points which belongs to more than one region forms lines and points colored black.
There is an algorithm which computes the Voronoi Diagram in O(nlog(n)), but it is infamous to be very complicated and hard. In fact, we are lenient problem setters, so we set n≤2000n≤2000, which means you can solve this task with slower Voronoi Diagram algorithms!
In this task, you should solve the point query problem in Voronoi diagram: in the Voronoi diagram constructed with the set of points {P1,P2,⋯,Pn}, you should determine which region(s) the point belongs in. More precisely, you will be given q queries of points. For each query point, you should determine the following:
In the first line, the number of points consisting Voronoi diagram nn, and the number of queries qq are given. (3≤n≤2 000,1≤q≤250 0003≤n≤2 000,1≤q≤250 000)
In the iith line of next nn lines, two integers indicating xx and yy co-ordinate of PiPi are given. These are the points consisting the Voronoi diagram. All nn points are distinct. (|x|,|y|≤104|x|,|y|≤104)
In the jjth line of next qq lines, two integers indicating xx and yy co-ordinate of QjQj are given. For each point QjQj, you should determine in which region(s) the given point belongs to. (|x|,|y|≤104|x|,|y|≤104)
Output consists of qq lines. In the jjth line, you should print one of following:
1 | 4 3 |
1 | LINE 1 2 |
From the description above we can draw that the Voronoi Diagram is drawn not casually but with some rules and the role can only correspond to one kind of the diagram. The rules are:
So for this problem, you just need to calculate the distance of the point to any previous given points. To determine whether it belongs to one or more region.
1 |
|