题目165：交叉点
本帖最后由 欧拉计划 于 2016-9-15 00:15 编辑Intersections
A segment is uniquely defined by its two endpoints.
By considering two line segments in plane geometry there are three possibilities:
the segments have zero points, one point, or infinitely many points in common.
Moreover when two segments have exactly one point in common it might be the case that that common point is an endpoint of either one of the segments or of both. If a common point of two segments is not an endpoint of either of the segments it is an interior point of both segments.
We will call a common point T of two segments L1 and L2a true intersection point of L1 and L2 if T is the only common point of L1 and L2 and T is an interior point of both segments.
Consider the three segments L1, L2, and L3:
L1: (27, 44) to (12, 32)
L2: (46, 53) to (17, 62)
L3: (46, 70) to (22, 40)
It can be verified that line segments L2 and L3 have a true intersection point. We note that as the one of the end points of L3: (22,40) lies on L1 this is not considered to be a true point of intersection. L1 and L2 have no common point. So among the three line segments, we find one true intersection point.
Now let us do the same for 5000 line segments. To this end, we generate 20000 numbers using the so-called "Blum Blum Shub" pseudo-random number generator.
s0 = 290797
sn+1 = sn×sn (modulo 50515093)
tn = sn (modulo 500)
To create each line segment, we use four consecutive numbers tn. That is, the first line segment is given by:
(t1, t2) to (t3, t4)
The first four numbers computed according to the above generator should be: 27, 144, 12 and 232. The first segment would thus be (27,144) to (12,232).
How many distinct true intersection points are found among the 5000 line segments?
题目：
线段由两个端点唯一决定。
几何平面上若存在两条线段，则有下面三种可能：
线段有 0 个、1 个、无穷个交点。
另外，如果它们有一个交点时，这个交点可能是两条线段中一条或两条的端点。如果这个交点不是任一线段的端点的话，那么这个交点就是这两条线段的内部点。
如果交点 T 是 L1 和 L2 的唯一交点，而且是内部点，那么，我们把 T 叫做 L1，L2 线段的真交叉点。
考虑下面三条线段：
L1: (27, 44) 到 (12, 32)
L2: (46, 53) 到 (17, 62)
L3: (46, 70) 到 (22, 40)
可以证明，L2 和 L3 有一个真交叉点。我们注意到 L3 的一个端点 (22,40) 就在 L1 上，所以，它不是真交叉点。L1 和 L2 没有交点。所以，这三条线段之间总共只有一个真交叉点。
现在我们对 5000 条线段做同样的分析。最后，我们使用一个叫做 "Blum Blum Shub" 的伪随机数生成器，生成 20000 个数字。
s0 = 290797
sn+1 = sn×sn (modulo 50515093)
tn = sn (modulo 500)
为了创建线段，我们使用四个连续的数字 tn。即第一条线段定义如下：
(t1, t2) 到 (t3, t4)
根据上面生成器，前四个数字应该是 27，144，12，232。所以，第一条线段应该是从 (27,144) 到 (12,232)。
请问，在这 5000 条线段中，有多少个不同的真交叉点？
页:
[1]