当前位置：首页 > web >正文

AcWing 3690：求交点 ← 复旦大学考研机试题 + 克莱姆法则

web 2025/8/11 12:44:03

【题目来源】
https://www.acwing.com/problem/content/3693/

【题目描述】
求直线交点，输入两个直线上的各两个端点，求其交点，若无交点或无穷个交点输出一句 Parallel or coincident，输出交点保留两位小数。

【输入格式】
第一行包含四个整数 x1,y1,x2,y2，表示第一个直线上的两个点坐标。
第二行包含四个整数 x3,y3,x4,y4，表示第二个直线上的两个点坐标。

【输出格式】
输出两个直线的交点坐标，保留两位小数。
若无交点或无穷个交点输出一句 Parallel or coincident。

【数据范围】
0≤xi,yi≤10

【输入样例】
0 0 5 5
0 2 2 0

【输出样例】
1.00 1.00

【算法分析】
● 克莱姆法则（Cramer's Rule）求两条直线交点坐标的步骤如下。
步骤一：整理线性方程组
将直线方程整理成标准线性方程组形式： $\begin{cases} a_1x + b_1y =c_1 \\ a_2x + b_2y =c_2 \end{cases}$

步骤二：计算系数行列式 D
$D = \begin{vmatrix} a_1 & b_1 \\ a_2 & b_2 \\ \end{vmatrix} = a_1b_2 - a_2b_1$
如果 D=0‌：两条直线‌平行或重合‌，无交点或有无穷多交点。
如果 D≠0‌：两条直线‌相交‌，可以继续按照步骤三、步骤四求解。

步骤三：计算 Dx 和 Dy
$D_x = \begin{vmatrix} c_1 & b_1 \\ c_2 & b_2 \\ \end{vmatrix} =c_1b_2 - c_2b_1$ $D_y = \begin{vmatrix} a_1 & c_1 \\ a_2 & c_2 \\ \end{vmatrix} = a_1c_2 - a_2c_1$

步骤四：求解 x 和 y‌
$x = \frac{D_x}{D} = \frac{c_1b_2 - c_2b_1}{a_1b_2 - a_2b_1}$ $y = \frac{D_y}{D} = \frac{a_1c_2 - a_2c_1}{a_1b_2 - a_2b_1}$

● 已知两条直线各两个点的坐标，利用克莱姆法则计算它们的交点坐标
步骤一：给定两条直线所经过的点的坐标
直线 L1 经过点 A(x1, y1) 和 B(x2, y2)，直线 L2 经过点 C(x3, y3) 和 D(x4, y4)。

步骤二：写出直线的两点式方程： $\frac{y - y_1}{x - x_1} = \frac{y_2 - y_1}{x_2 - x_1}$

步骤三：整理直线的两点式方程
$(y_2-y_1)(x-x_1)=(x_2-x_1)(y-y_1)$
$(y_2 - y_1)x+(x_1 - x_2)y=x_1 y_2 - x_2 y_1$
所以，针对直线 L1，可令 $a_1 = y_2 - y_1, \quad b_1 =x_1- x_2, \quad c_1 = x_1 y_2 - x_2 y_1$
相应的，对直线 L2，可得 $a_2 = y_4 - y_3, \quad b_2 =x_3- x_4, \quad c_2 = x_3 y_4 - x_4 y_3$

步骤四：依据克莱姆法则求解
d=(y2-y1)*(x3-x4)-(y4-y3)*(x1-x2)
dx=(x1*y2-x2*y1)*(x3-x4)-(x3*y4-x4*y3)*(x1-x2)
dy=(x3*y4-x4*y3)*(y2-y1)-(x1*y2-x2*y1)*(y4-y3)
则，x=dx/d，y=dy/d。

● 如上各公式的 LaTex 代码如下所示。

\begin{cases} a_1x + b_1y =c_1 \\ a_2x + b_2y =c_2 \end{cases}D = \begin{vmatrix} a_1 & b_1 \\ a_2 & b_2 \\ \end{vmatrix} = a_1b_2 - a_2b_1D_x = \begin{vmatrix} c_1 & b_1 \\ c_2 & b_2 \\ \end{vmatrix} =c_1b_2 - c_2b_1D_y = \begin{vmatrix} a_1 & c_1 \\ a_2 & c_2 \\ \end{vmatrix} = a_1c_2 - a_2c_1x = \frac{D_x}{D} = \frac{c_1b_2 - c_2b_1}{a_1b_2 - a_2b_1}y = \frac{D_y}{D} = \frac{a_1c_2 - a_2c_1}{a_1b_2 - a_2b_1}---------------------------------------------------------------\frac{y - y_1}{x - x_1} = \frac{y_2 - y_1}{x_2 - x_1}(y_2-y_1)(x-x_1)=(x_2-x_1)(y-y_1)(y_2 - y_1)x+(x_1 - x_2)y=x_1 y_2 - x_2 y_1a_1 = y_2 - y_1, \quad b_1 =x_1- x_2, \quad c_1 = x_1 y_2 - x_2 y_1a_2 = y_4 - y_3, \quad b_2 =x_3- x_4, \quad c_2 = x_3 y_4 - x_4 y_3

● 浮点数计算的精度限制，导致理论上的零值可能表示为 -0.0。所以，在输出前对结果进行阈值判断或取绝对值，确保符号一致性。

● 全局变量 y1 会和 cmath 标准库中的变量产生冲突。
资料显示，j0、j1、jn、y0、y1、yn 等全局变量都会和 cmath 标准库中相应变量产生冲突。
解决方法为“将 j0、j1、jn、y0、y1、yn 设为局部变量”。
详见：https://blog.csdn.net/hnjzsyjyj/article/details/140464618

【算法代码】

#include <bits/stdc++.h>
using namespace std;int main() {int x1,y1,x2,y2;int x3,y3,x4,y4;cin>>x1>>y1>>x2>>y2;cin>>x3>>y3>>x4>>y4;int d=(y2-y1)*(x3-x4)-(y4-y3)*(x1-x2);if(d==0) {cout<<"Parallel or coincident"<<endl;return 0;}double dx=(x1*y2-x2*y1)*(x3-x4)-(x3*y4-x4*y3)*(x1-x2);double dy=(x3*y4-x4*y3)*(y2-y1)-(x1*y2-x2*y1)*(y4-y3);double x=dx/d;double y=dy/d;//Process problem of -0.00if(fabs(x)<1e-10) x=0.0;if(fabs(y)<1e-10) y=0.0;printf("%.2lf %.2lf",x,y);return 0;
}/*
in:
0 0 0 1
1 0 7 0out:
0.00 0.00
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/140464618
https://www.acwing.com/solution/content/245597/
https://www.acwing.com/solution/content/54959/

查看全文

http://www.xdnf.cn/news/17186.html