algorithm - 给定平面上的两条线，如何找到最接近它们交点的整数点？

Question

我无法解决:

给你 8 个整数:

• A、B、C 表示平面上的一条线，方程为 Ax + By = C
• a,b,c代表另一条线
• x,y代表平面上的一点

这两条线不平行，因此将平面分成 4 block 。点 (x, y) 位于这些碎片中。

问题:
编写一个快速算法，在与 (x,y) 相同的片段中找到一个具有整数坐标的点，该点最接近两条给定线的交叉点。

注意:
这不是作业，这是老Euler - 我完全不知道如何处理的类型任务。

更新:您可以假设输入的 8 个数字是 32 位有符号整数。但是您不能假设解决方案是 32 位的。

更新 2:困难的情况 - 当线几乎平行时 - 是问题的核心

更新 3:该问题的作者指出解决方案是线性 O(n) 算法。其中 n 是输入的大小(以位为单位)。即:n = log(A) + log(B) + ... + log(y)
但是我还是解决不了。

请说明已发布算法的复杂性(即使它们是指数级的)。

Answer 1

alt text http://imagebin.ca/img/yhFOHb.png

Diagram

找到线 L1:Ax+By=C 和 L2:ax+by=c 的交点后，即点 A(x1,y1).

再定义两条平行于X轴的线y = ceil(y1)和y = floor(y1)并找到它们的交点与 L1 和 L2 即点 B(x2,y2) 和 C(x3,y3)。

那么你需要的点是 D 或 E 哪个更接近点 A。类似的程序适用于飞机的其他部分。

D ( ceil(x2), ceil(y1)  )
E ( ceil(x3), floor(y1) )