HBC232892[JSOI2011]柠檬,dp的优化,栈,单调队列单调栈,数据结构,动态规划Nearest Point题解

庄子墨算法基础篇 2023-11-26 05:26:01 102 0

想要检验自己的编程水平？来试试全网最全C++题库，让您在挑战中不断进步。

Calculating the neatest point is known to be difficult. Therefore, there are many heuristic methods proposed. The following describes one of these algorithms:. , the algorithm takes the point that is closest to. .x∣. If there are multiple such points, the point with the smallest index will be selected.α is selected as 0, the coordinates of these three points after the rotation are. (1,1),(3,3),(0,2), respectively, and thus the nearest points to. , the coordinates of these three points after the rotation are. represents the probability for the algorithm to take

Nearest point is a classical problem in computational geometry. Given a set S S of n n points p_1, . . . , p_n, p_j p 1 ,...,p n ,p j is the nearest point of pi if (1) j neq i (1)j  =i , and (2) (2) for any other point p_k (knotin{i, j}), dis(p_i , p_j ) ≤ dis p k (k  ∈i,j),dis(p i ,p j )≤dis (p_i , p_k) (p i ,p k ) , where dis dis (p_1, p_2) (p 1 ,p 2 ) is defined as sqrt{(p_1.x − p_2.x)^2 + (p_1.y − p_2.y)^2} (p 1 .x−p 2 .x) 2 +(p 1 .y−p 2 .y) 2 in a 2-D 2−D space. Calculating the neatest point is known to be difficult. Therefore, there are many heuristic methods proposed. The following describes one of these algorithms: • Step1: A random angle α α is uniformly selected from range [−π, π) [−π,π). • Step2: All points in S S are rotated α α counterclockwise centered on the origin (0, 0) (0,0). • Step3: For each point p_i p i , the algorithm takes the point that is closest to p_i p i on the x-coordinate, i.e x−coordinate,i.e., the point p_j (i neq j) p j (i  =j) that minimizes |p_i .x − p_j .x| ∣p i .x−p j .x∣. If there are multiple such points, the point with the smallest index will be selected. For example, suppose there are three points p_1 = (1, 1) p 1 =(1,1), p_2 = (3, 3) p 2 =(3,3), and p_3 = (0, 2) p 3 =(0,2) in set S S. 1. When α α is selected as 0, the coordinates of these three points after the rotation are (1, 1),(3, 3),(0, 2) (1,1),(3,3),(0,2), respectively, and thus the nearest points to p_1, p_2, p_3 p 1 ,p 2 ,p 3 found by the algorithm are p_3, p_1, p_1 p 3 ,p 1 ,p 1 , respectively. 2. When α α is selected as frac{π}4 4 π , the coordinates of these three points after the rotation are (0, sqrt2),(0, 3 sqrt 2),(− sqrt 2, sqrt 2) (0, 2 ),(0,3 2 ),(− 2 , 2 ), and thus the nearest points are p_2, p_1, p_1 p 2 ,p 1 ,p 1 , respectively. Now, given the n n points p_1, . . . , p_n p 1 ,...,p n in S S, your task is to output an n × n n×n matrix w w, where w_{i,j} w i,j represents the probability for the algorithm to take p_j p j as the nearest point of p_i p i .