POJ 1269 Intersecting Lines【浮点几何运算】_综合

题目

We all know that a pair of distinct points on a plane defines a line and that a pair of lines on a plane will intersect in one of three ways: 1) no intersection because they are parallel, 2) intersect in a line because they are on top of one another (i.e. they are the same line), 3) intersect in a point. In this problem you will use your algebraic knowledge to create a program that determines how and where two lines intersect.
Your program will repeatedly read in four points that define two lines in the x-y plane and determine how and where the lines intersect. All numbers required by this problem will be reasonable, say between -1000 and 1000.

题目大意

给出四个点的坐标，前两点与后两点分别确定两条直线，判断两条直线的位置关系，如果相交，请给出交点坐标，保留两位小数。

输入

The first line contains an integer N between 1 and 10 describing how many pairs of lines are represented. The next N lines will each contain eight integers. These integers represent the coordinates of four points on the plane in the order $x_1y_1x_2y_2x_3y_3x_4y_4$ . Thus each of these input lines represents two lines on the plane: the line through $x_1,y_1)$ and $x_2,y_2)$ and the line through $x_3,y_3)$ and $x_4,y_4)$ . The point $x_1,y_1)$ is always distinct from $x_2,y_2)$ . Likewise with $x_3,y_3)$ and $x_4,y_4)$ .

输出

There should be N+2 lines of output. The first line of output should read INTERSECTING LINES OUTPUT. There will then be one line of output for each pair of planar lines represented by a line of input, describing how the lines intersect: none, line, or point. If the intersection is a point then your program should output the x and y coordinates of the point, correct to two decimal places. The final line of output should read “END OF OUTPUT”.

样例输入

5
0 0 4 4 0 4 4 0
5 0 7 6 1 0 2 3
5 0 7 6 3 -6 4 -3
2 0 2 27 1 5 18 5
0 3 4 0 1 2 2 5

样例输出

INTERSECTING LINES OUTPUT
POINT 2.00 2.00
NONE
LINE
POINT 2.00 5.00
POINT 1.07 2.20
END OF OUTPUT

题目分析

此题重在先判断两直线的关系，即可先确定二者斜率 $k$ ,判定直线是否有可能平行或者重合。若斜率不一致，则可通过联立方程 $\begin{cases} y=k_1\times x+b_1 \\ y=k_2\times x + b_2 \end{cases}$
得到 $\begin{cases} x= \frac{b_1-b_2}{k_2-k_1} &if&k_1,k_2 存在 \\ y= k_1 \times x+b_1 \end{cases}$
斜率一致也分两种情况讨论，1)斜率都不存在；2)斜率都存在。第一种情况比较 $x_1,x_3$ 即可，第二种情况则需计算出对应的y值再做比较。

代码

#include <iostream>
using namespace std;
double x,y,k1,k2,b1,b2;
int x1,x2,x3,x4,y1,y2,y3,y4; 
void cal(){
    //计算交点b1=y1-k1*x1;b2=y3-k2*x3;x=(b1-b2)/(k2-k1);y=k1*x+b1;
}double abs(double m){
    //取绝对值if((m-0)<=1e-6) return -m;return m;
}int main() {
    int T;cin >> T;cout <<"INTERSECTING LINES OUTPUT"<<endl;while(T--){
    int flag1 = 1,flag2 = 1;cin >>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;if(x1==x2) flag1=0;//第一条直线斜率不存在if(x3==x4) flag2=0;//第二条直线斜率不存在if(flag1==flag2&&flag1==0){
    //斜率都不存在if(x1 == x3) cout << "LINE"<<endl;else cout <<"NONE"<<endl;}else if(flag1==flag2&&flag1!=0){
    //斜率都存在k1=(double)(y2-y1)/(x2-x1);k2=(double)(y4-y3)/(x4-x3);if(abs(k1-k2)<=1e-6){
    //比较斜率是否相同k2=(double)(y3-y2)/(x3-x2);if(abs(k1-k2)<=1e-6) cout <<"LINE"<<endl;else cout <<"NONE"<<endl;}else{
    cal();cout <<"POINT ";printf("%.2f %.2f\n",x,y);}}else if(flag1!=flag2){
    //斜率不同，但有一条直线斜率不存在if(flag1==0){
    k2=(double)(y4-y3)/(x4-x3);b2=y3-k2*x3;x = x1;y = k2*x+b2;}if(flag2==0){
    k1=(double)(y2-y1)/(x2-x1);b1=y1-k2*x1;x = x3;y = k1*x+b1;}cout <<"POINT ";printf("%.2f %.2f\n",x,y);}}cout <<"END OF OUTPUT"<<endl;return 0;
}

运行结果

在这里插入图片描述

题目链接

http://poj.org/problem?id=1269