Fork me on GitHub

POJ 1269 Intersecting Lines (计算几何)

题目

Description

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$ .

Input

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)$ .

Output

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” .

Sample Input

1
2
3
4
5
6
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

Sample Output

1
2
3
4
5
6
7
INTERSECTING LINES OUTPUT
POINT 2.00 2.00
NONE
LINE
POINT 2.00 5.00
POINT 1.07 2.20
END OF OUTPUT

题意

给出两条直线( $4$ 个点),要求判断出这两条直线的关系:平行,同线,相交。如果相交还要求出交点坐标。


分析

先判断是否共线,否则判断是否平行,否则只能相交,求出交点。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<cstdlib>
#include<functional>
#include<climits>
#include<cctype>
#include<iomanip>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define mod 1e9+7
#define clr(a,x) memset(a,x,sizeof(a))
const double eps = 1e-6;
struct point
{
int x,y;
};
point a;
point b;
point c;
point d;
double cross(point a,point b,point c)
{
return (c.y-a.y)*(b.x-a.x)-(b.y-a.y)*(c.x-a.x);
}
void solve(point a,point b,point c,point d)
{
if(fabs(cross(a,b,c))<=eps && fabs(cross(a,b,d))<=eps)
printf("LINE\n");
else if((b.x-a.x)*(d.y-c.y)==(d.x-c.x)*(b.y-a.y))
printf("NONE\n");
else
{
double a1=a.y-b.y;
double b1=b.x-a.x;
double c1=a.x*b.y-b.x*a.y;
double a2=c.y-d.y;
double b2=d.x-c.x;
double c2=c.x*d.y-d.x*c.y;
double x=(b1*c2-b2*c1)/(a1*b2-a2*b1);
double y=(a2*c1-a1*c2)/(a1*b2-a2*b1);
printf("POINT %.2lf %.2lf\n",x,y);
}
}
int main()
{
int t;
while(cin>>t)
{
cout<<"INTERSECTING LINES OUTPUT"<<endl;
for(int i=0;i<t;i++)
{
cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y>>d.x>>d.y;
solve(a,b,c,d);
}
cout<<"END OF OUTPUT"<<endl;
}
return 0;
}
-------------本文结束感谢您的阅读-------------
obsidian wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
坚持原创技术分享,您的支持是我最大的动力!