我必须为以下问题设计一个运行时间为 O(nlogn) 的算法:
给定 n 个点的集合 P,确定值 A > 0 使得剪切变换 (x,y) -> (x+Ay,y) 不会改变具有不等 x 坐标的点的顺序(在 x 方向上) .
我什至很难弄清楚从哪里开始。
对此的任何帮助将不胜感激!
谢谢!
我必须为以下问题设计一个运行时间为 O(nlogn) 的算法:
给定 n 个点的集合 P,确定值 A > 0 使得剪切变换 (x,y) -> (x+Ay,y) 不会改变具有不等 x 坐标的点的顺序(在 x 方向上) .
我什至很难弄清楚从哪里开始。
对此的任何帮助将不胜感激!
谢谢!
好的,这是一个粗略的方法。
按 x 顺序对点列表进行排序。(这给出了 O(nlogn)——以下所有步骤都是 O(n)。)
生成 dx_i = x_(i+1) - x_i 的新列表,即 x 坐标之间的差异。由于 x_i 是有序的,所有这些 dx_i >= 0。
现在对于某些 A,转换后的 dx_i(A) 将是 x_(i+1) -x_i + A * ( y_(i+1) - y_i)。如果这是负数或零 (x_(i+1)(A) < x_i(A).
因此,对于每个 dx_i,找到使 dx_i(A) 为零的 A 值,即 A_i = - (x_(i+1) - x_i)/(y_(i+1) - y_i)。您现在有一个系数列表,这些系数将“导致”连续(按 x 顺序)点对之间的顺序交换。注意除以零,但在两个点具有相同 y 的情况下,这些点不会改变顺序。一些 A_i 将是负数,根据需要丢弃这些 A>0。(负 A_i 也会导致订单交换,所以 A>0 的要求有点武断。)
在列表中找到最小的 A_i > 0。因此,任何 0 < A < A_i(min) 的 A 都将是一个不会改变点顺序的剪切。选择 A_i(min) 因为这会将两个点带到相同的 x,但不会彼此过去。
假设所有 x,y 坐标都是正数。(不失一般性,可以添加偏移量。)在时间 O(n log n) 内,对点列表 L 进行排序,主要按 x 坐标升序,其次按 y 坐标升序。在时间 O(n) 中,处理点对(按 L 顺序)如下。令p、q为L中任意两个连续点,令px、qx、py、qy分别表示它们的x、y坐标值。从那里你只需要考虑几种情况,应该做什么就很明显了:如果 px=qx,什么也不做。否则,如果 py<=qy,则什么也不做。否则 (px>qx, py>qy) 要求 px + A*py < qx + A*qy,即(px-qx)/(py-qy) > A。
所以:按顺序遍历 L,找到所有 px>qx 和 py>qy 的点对都满足的最大 A'。然后选择比 A' 小一点的 A 值,例如 A'/2。(或者,如果问题的目标是找到最大的此类 A,则只需报告 A' 值。)
我认为 y = 0。
When x = 0, A > 0
(x,y) -> (x+Ay,y)
-> (0+(A*0),0) = (0,0)
When x = 1, A > 0
(x,y) -> (x+Ay,y)
-> (1+(A*0),0) = (1,0)
x坐标不等,(2,0), (3,0), (4,0)...所以,我认为起点可能是(0,0),x=0。