设$A=(x_1,y_1)$、$B=(x_2,y_2)$是线段的两个端点，则该线段所在直线方程是
$$L_{AB}(x,y)=0,$$
其中
$$L_{AB}=(x_2-x_1)(y-y_1)-(y_2-y_1)(x-x_1).$$
若线段AB和线段CD有真交点，则C和D分别在直线AB的两侧，同理A和B也分别在C和D的两侧，即使
$$L_{AB}(C)L_{AB}(D) < 0, \quad L_{CD}(A)L_{CD}(B) < 0.$$
若一条线段的端点在另一条线段所在的直线上，那么将段点坐标代入直线方程将得到0，因此以上已经排除了这一情形。
若上式成立，那么进一步联立两直线方程以计算交点坐标，此过程即求一2阶矩阵的逆（未学过线性代数的可以消元计算）：
$$\begin{cases}ax+by=u \\ cx+dy=u\end{cases} \Rightarrow \begin{pmatrix}x \\ y\end{pmatrix}=\frac{1}{ad-bc}\begin{pmatrix}d & -b \\ -c & a\end{pmatrix}\begin{pmatrix}u \\ v\end{pmatrix}=\frac{1}{ad-bc}\begin{pmatrix}du-bv \\ av-cu\end{pmatrix},$$
按要求生成所有端点，双循环考察所有线段并按真交点的坐标去重后即得结果$2868868$。
注：本题涉及的直线划分平面的知识是我国本科《解析几何》课程的标准内容。
import fractions
s=290797
p=[]
while len(p) < 5000:
p.append([])
for i in range(4):
s=(s*s)%50515093
p[-1].append(s%500)
def check(p1,p2):
x1,y1,x2,y2=p1
a,b,c,d=p2
return ((x2-x1)*(b-y1)-(y2-y1)*(a-x1))*((x2-x1)*(d-y1)-(y2-y1)*(c-x1)) < 0
def solve(p1,p2):
x1,y1,x2,y2=p1
a,b,u=y1-y2,x2-x1,(x2-x1)*y1-(y2-y1)*x1
x1,y1,x2,y2=p2
c,d,v=y1-y2,x2-x1,(x2-x1)*y1-(y2-y1)*x1
return d*u-b*v,a*v-c*u,a*d-b*c
r=set()
for i in range(4999):
for j in range(i+1,5000):
if check(p[i],p[j]) and check(p[j],p[i]):
x,y,z=solve(p[i],p[j])
r.add((fractions.Fraction(x,z),fractions.Fraction(y,z)))
print len(r)
|
