我解决不了:
你得到8个整数:
两条线不平行,因此将平面分成4块.点(x,y)位于这些部件的内部.
问题:
编写一个快速算法,找到与(x,y)相同的整数坐标的点,该点最接近两条给定线的交叉点.
注意:
这不是作业,这是古老的欧拉式任务,我完全不知道如何处理.
更新: 您可以假设输入的8个数字是32位有符号整数.但你不能假设解决方案是32位.
更新2: 困难的情况 - 线条几乎平行 - 是问题的核心
更新3:
问题的作者声明解决方案是线性O(n)算法.其中n是输入的大小(以位为单位).即:n = log(A)+ log(B)+ ... + log(y)
但我仍然无法解决它.
请说明已发布算法的复杂性(即使它们是指数级的).
alt text http://imagebin.ca/img/yhFOHb.png
你之后找到线的交叉L1:Ax+By=C和L2:ax+by=c即点A(x1,y1).
定义两个更多的行y = ceil(y1)和y = floor(y1)平行于X-axis并且发现它们与交叉路口L1和L2即点B(x2,y2)和C(x3,y3).
然后指出你需要是D或E更接近点A.类似的程序适用于飞机的其他部分.
D ( ceil(x2), ceil(y1) )
E ( ceil(x3), floor(y1) )
此问题属于Integer Convex Optimization类别.
这里介绍的是解决问题的数学方法.我不指望你真正使用它 - 需要很多复杂的技术,而其他算法方法(例如"搜索"适当的点)可能会很好.然而,人们对"真正的"解决方案表达了兴趣,所以在这里.
它可以分三个阶段解决:
我在这里展示如何解决这个问题的"困难"实例.我认为这种方法可以推广.我在原帖的评论中加入了另一个更简单的例子.
考虑两行:
10000019 * X - 10000015 * Y + 909093 >= 0 (L1)
-10000022 * X + 10000018 * Y + 1428574 >= 0 (L2)
A = 10000019, B = -10000015, C = -909093
交点是H:
Hx = -5844176948071/3, Hy = -5844179285738/3
对于点M(X,Y),平方距离HM ^ 2是:
HM^2 = (9*X^2+35065061688426*X
+68308835724213587680825685
+9*Y^2+35065075714428*Y)/9
g = gcd(A,B)= 1:L1的等式A*X+B*Y+909093
可以取任何整数值.
Bezout系数,U = 2500004和V = 2500005验证:
A * U + B * V = 1
我们现在在"双重"基础(K,T)中重写问题,定义如下:
X = T*U - K*B
Y = T*V + K*A
替换后,我们得到:
T+909093 >= 0
2*T+12*K+1428574 >= 0
minimize 112500405000369*T^2
+900003150002790*T*K
+1800006120005274*K^2
+175325659092760325844*T
+701302566240903900522*K
+Constant
在进一步翻译之后(首先在T上,然后在K上以使第二个等式中的常数最小化),T = T1-909093,K = K1 + 32468:
T1 >= 0
2*T1+4+12*K1 >= 0
minimize 112500405000369*T1^2
+300001050000930*T1
+900003150002790*T1*K1
+1200004080003516*K1
+1800006120005274*K1^2
+Constant
我提出的算法是在T1上循环.实际上,我们不需要在这里循环,因为最好的结果是由T1 = K1 = 0给出,对应于:
X = -1948055649352, Y = -1948056428573
我在下面的帖子.
这是算法的另一个想法.它可能有用,但我没有实现它......
通过适当改变符号以匹配(x,y)的位置,可以写出问题:
A*X+B*Y>=C (line D)
a*X+b*Y>=c (line d)
minimize the distance between M(X,Y) and H, the intersection point
A*b != a*B (intersection is defined)
A,B,C,a,b,c,X,Y all integers
由(A X + B Y)到达的所有值的集合是g = gcd(A,B)的所有倍数的集合,并且存在整数(u,v),使得A u + B v = g(Bezout)定理).从具有整数坐标(X0,Y0)的点开始,对于所有整数K,具有整数坐标和相同的A X + B Y 值的所有点都是(X0-K B/g,Y0 + K A/g).
为了解决这个问题,我们可以在与H相加的距离上循环与D平行的线,并且包含具有整数坐标的点.
计算g,u,v和H(可能不需要H的坐标,我们只需要与距离对应的二次形式的系数).
T0 = ceil(C/g)
从T = T0循环
一个.找K最小(或最大,取决于B-b A 的符号)整数验证a*(T u-K B/g)+ b*(T v + K A/g)> = c
湾 如果更接近H ,保持点(T u -K B/g,T v + K A/g)
C.当(T-T0)对应于D的距离大于目前为止的最佳结果时退出循环,否则继续T + = 1
Phi*_*hil -1
我认为这有3部分。
计算两条线的交点，并保留该点的 X 和 Y 坐标
找到给定点所在的部分。这应该很容易，因为您有两条线的斜率，以及由给定点和交点创建的线的斜率。给他们打电话m_line1，m_line2并且m_intersect。如果m_intersect有一个公式可以使用这些值和给定点的位置计算出该部分。
至少这些是我采取的步骤。
更新以添加更多内容
好的，我将首先讨论#2。
如果计算给定点和交点的斜率，则得出m_intersection。这是穿过交点的直线的斜率。假设m_line1是 2 个斜率中较大的一个，因此当 x 在相交后增加时，line1 位于 line2 的“上方”。它使得更容易考虑部分名称。对于大于交点坐标 x 的 x，我们将线 1 和线 2 之间的条子给出的部分称为A部分，然后我们将按顺时针方向命名其他 3 个部分，以便A和C彼此相对。
如果m_intersection介于m_line1和之间m_lin2，则它必须位于A或C 2 个部分之一。哪个部分是 x 坐标值相对于交叉点的 x 坐标的简单测试。我们将A定义为具有较大价值的部分。如果斜率在m_line1或之外，可以进行类似的计算m_line2。
这给了你你的点所在的部分。你所做的只是计算 1 个交集（5 个乘法、2 个除法和少量减法，如果你按照传统方式进行）、3 个斜率，然后进行几个整数比较。
编辑 #3 - 根据（非）大众需求支持！
下面是我计算#3 的方法，即距离交点最近的整数点。它可能不是最好的，但它使用二分搜索，所以它是 O(log n)，其中 n 与线斜率差的倒数有关。它们距离越近，n 越大。
首先，计算两条线的斜率之差。说是1/8。这意味着从交点开始，必须沿 x 轴移出 8 个单位，才能保证两条线之间的 y 轴上有一个整数（可能在其中一条线上）。现在，如果交集本身不在整数 x 坐标上，那么您需要进一步确定起点位于整数 x 坐标上，但它是有界的。如果交点位于 x = 1.2，那么在上面的示例中，最坏的情况是从 x = 41 开始，然后沿 y 轴向下移动约 5 个单位。选择您获得的 y 值的上限或下限。这并不是非常关键。
现在你有了一个起点，可以通过二分搜索来近似最近的点。新线段位于交点和起点之间，移动单位是该线段斜率的倍数。计算线段的中点，看看它是否位于两条线之间。如果不是直接命中，则加或减 1，如果其中任何一个命中，则将剩余距离减半，然后再做一次。否则搜索该段的另一半。
如果坡度差不小于 1，我认为问题可能会更简单（暴力破解交叉点周围的空间）。但这只是上面搜索的一个特例，您不需要走那么远来找到起点。