计算两组序列的交点（线）

Question

我必须找到一种算法，它可以找到两组数组之间的交集总数，而其中一个数组是排序的。

一个例子，我们有这两个数组，我们画直线朝向相应的数字。

这两个阵列总共给我们提供了7个交点。

它存在什么样的算法来帮助我解决这个问题？

我已经使用搜索按钮，但没有找到任何可以解决这个问题的东西。

感谢

Answer 1

给定两个数M和N中，线不会相交如果

• 顶端M是到前N个的右侧，底部M是到的权最后N个
• 顶端M是到前N的左侧，并且底部M是至底部的左移N

在其它两种情况：

• 左上角，右下角
• 右上，左下

线做相交。

在该示例中，8位于顶行的所有4位数字的左侧，右侧是3位数字的底部，因此8位与三位数字相交。

5位于顶部8的右侧，底部8的左侧，给出一个交叉点。 5是左边4和1顶部，右边4和1底部，再给出两个。所以5与三个数字相交。

请注意，我们计算了两次5和8的交点。实际上每个十字路口都会被计算两次。如果你完成了这个例子，你会计算14个交点。最后除以2得到答案。

Answer 2

可以代表每行y=a+bx，然后通过比较它们的y值比较各行的人。

每条线最多有一个相交线。