The 2023 ICPC Asia Hong Kong Regional Programming Contest (The 1st Universal Cup, Stage 2:Hong Kong) |
---|
Закончено |
The closest pair of points problem is a well-known problem of computational geometry. In this problem, there are $$$n$$$ points $$$p_1,p_2,\ldots,p_n$$$ in the Euclidean plane. You will be given $$$q$$$ queries. In the $$$i$$$-th query, you will be given two integers $$$\ell_i$$$ and $$$r_i$$$ ($$$1\leq \ell_i< r_i\leq n$$$). You need to find a pair of points $$$(u,v)$$$ such that $$$\ell_i\leq u<v\leq r_i$$$ and the Euclidean distance $$$\sqrt{(x_u-x_v)^2+(y_u-y_v)^2}$$$ between point $$$p_u$$$ and $$$p_v$$$ is minimized.
The first line of the input contains two integers $$$n$$$ and $$$q$$$ ($$$2 \leq n\leq 250\,000$$$, $$$1\leq q\leq 250\,000$$$), denoting the number of points and the number of queries.
In the next $$$n$$$ lines, the $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1\leq x_i,y_i\leq 10^8$$$), describing the coordinates of $$$p_i$$$.
Each of the next $$$q$$$ lines contains two integers $$$\ell_i$$$ and $$$r_i$$$ ($$$1\leq \ell_i< r_i\leq n$$$), denoting a query.
For each query, print a single line containing an integer, denoting the value of $$$(x_u-x_v)^2+(y_u-y_v)^2$$$.
5 5 2 4 1 1 3 3 5 1 4 2 1 5 2 3 2 4 3 5 1 3
2 8 8 2 2
2 1 1 1 1 1 1 2
0
Название |
---|