【POJ-1269】解题报告（计算几何，直线相交求交点）

原始题目

Intersecting Lines

  • Time Limit: 1000MS
  • Memory Limit: 10000K
  • Total Submissions: 18318
  • Accepted: 7816

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 x1y1x2y2x3y3x4y4. Thus each of these input lines represents two lines on the plane: the line through (x1,y1) and (x2,y2) and the line through (x3,y3) and (x4,y4). The point (x1,y1) is always distinct from (x2,y2). Likewise with (x3,y3) and (x4,y4).

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

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

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

Source

Mid-Atlantic 1996

题目大意

给出n组两点确定的直线（不是线段），判断两条直线是平行，相交（给出交点）还是同一直线。

解题思路

  • 计算几何基础题
  • 先求两向量\(v\_1,v\_2\)的cross（叉积），若为零则从两条直线的点各取一个构成向量\(v\_3\)和原向量其中一个求叉积，若也为零说明共线，不为零说明平行
  • 非上述则求交点，套模板公式即可

解题代码

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
//计算几何模板，二维几何基础
//使用印用注意避免直接在程序中调用构造函数构造无名对象。否则可能会导致程序出错 
//#include <bits/stdc++.h>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <set>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <map>
#include <string>
#define INF 0x3f3f3f3f
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
using namespace std;
typedef long long ll;
const double eps =1e-10;
const int maxn=50;
int n;
//有的命名为sgn函数，高精度符号判断 
int dcmp(double x){
	//相等函数判断，减少精度问题 
	if(fabs(x)<eps) return 0;
	else return x<0?-1:1;
}

//点的定义 
class Point{
	public:
	double x,y;
	Point (double x=0,double y=0):x(x),y(y){} //构造函数，方便代码的编写 
}point[maxn]; 

typedef Point Vector;// 从程序实现上，Vector只是Point的别名

//运算符重载 
Vector operator + (const Vector &A,const Vector &B) { return Vector(A.x+B.x,A.y+B.y); } //向量+向量=向量，点+向量=点
Vector operator - (const Vector &A,const Vector &B) { return Vector(A.x-B.x,A.y-B.y); } //向量-向量=向量，点-向量-点  
Vector operator * (const Vector &A,double p) { return Vector(A.x*p,A.y*p); }   			//向量*数=向量 （数乘） 
Vector operator / (const Vector &A,double p) { return Vector(A.x/p,A.y/p); }			//向量/数=向量 （数除）
double operator * (const Vector &A,const Vector &B) { return A.x*B.x+A.y*B.y; }			//向量（点乘）向量=数  （点乘）
bool operator < (const Point &A,const Point &B) { return A.x==B.x?A.y<B.y:A.x<B.x; } 	//按x值递增排序 
bool operator == (const Point &A,const Point &B) { return dcmp(A.x-B.x)==0&& dcmp(A.y-B.y)==0; } //判定两个点是否相同，用到dcmp精度判定 

//点乘叉乘 
double dot(const Vector &A,const Vector &B){ return A.x*B.x+A.y*B.y; }					//向量（叉乘）向量=向量 （叉乘） 
double operator ^ (const Vector &A,const Vector &B){ return A.x*B.y-A.y*B.x; }
double cross(const Vector &A,const Vector &B){ return A.x*B.y-A.y*B.x; }

//模长面积 
double abs(const Vector &A){ return sqrt(dot(A,A));}									//计算向量模长 
double area2(const Point &A,const Point &B,const Point &C){ return cross(B-A,C-A) ;} 	//计算平行四边形方向面积
double PolygonArea(Point *p,int n) { double area=0; rep(i,1,n-1){area+=cross(p[i]-p[0],p[i+1]-p[0]);}return area/2.0; }	//计算多边形的有向面积

//旋转
Vector rotate(Vector A,double rad) { return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));}  //旋转rad弧度 
Vector normal(Vector A){double l=abs(A);return Vector(-A.y/l,A.x/l);} 					//计算单位法线，左转90

//线段定义 
class Line {
	public:
		Point s,e;
		Line(){}
		Line(Point _s,Point _e){
			s=_s;e=_e;
		}
		
}line[maxn];
//判断两线段是否相交 
bool inter(Line l1,Line l2){
//	cout<<"L1  "<<l1.e.x<<","<<l1.e.y<<"   "<<l1.s.x<<","<<l1.s.y<<endl;
//	cout<<"L2  "<<l2.e.x<<","<<l2.e.y<<"   "<<l2.s.x<<","<<l2.s.y<<endl;
	return (
		//根据题目要求端点相交是否算作相交来决定大于等于和小于等于 
		//排斥实验 
		max(l1.s.x,l1.e.x)>=min(l2.s.x,l2.e.x) &&
		max(l2.s.x,l2.e.x)>=min(l1.s.x,l1.e.x) &&
		max(l1.s.y,l1.e.y)>=min(l2.s.y,l2.e.y) &&
		max(l2.s.y,l2.e.y)>=min(l1.s.y,l1.e.y) &&
		//跨立实验 
		dcmp((l2.s-l1.s)^(l1.s-l1.e))*dcmp((l2.e-l1.s)^(l1.s-l1.e))<0 &&
		dcmp((l1.s-l2.s)^(l2.s-l2.e))*dcmp((l1.e-l2.s)^(l2.s-l2.e))<0
	) ;
}
bool inter(Point a1,Point a2,Point b1,Point b2){
	Line l1(a1,a2),l2(b1,b2);
	return inter(l1,l2);
}
bool cmp(Point a,Point b){
	if(a.x==b.x) return a.y<b.y;
	else return a.x<b.x;
}

//求两直线交点
Point getinter(Line l1,Line l2){Vector v=l1.s-l1.e;Vector w=l2.s-l2.e;Vector u=l1.e-l2.e;double t=cross(w,u)/cross(v,w);return l1.e+v*t;} 
Point getinter(Point a1,Point a2,Point b1,Point b2){Line l1(a1,a2);Line l2(b1,b2);return getinter(l1,l2);}


//判定点和线段的关系，
//0:不在线段所在直线上
//1:在线段内（不含端点） 
//2:在线段端点
//3:在线段两侧的射线上 
int  online(Point a,Line l){
	if(dcmp(cross(l.s-a,l.e-a))!=0) return 0;
	double pans=dcmp(dot(l.s-a,l.e-a));
//	cout<<(l.s-a).x<<","<<(l.s-a).y<<"   "<<(l.e-a).x<<","<<(l.e-a).y<<endl;
	if(pans<0) return 1;
	else if(pans==0) return 2;
	else if(pans>0) return 3;
}
int online(Point a,Point b1,Point b2){
	Line l(b1,b2);
	return online(a,l);
}

//凸包
int ConvexHull(Point *p,int n,Point *ch)
{
	sort(p,p+n,cmp);
	int m=0;
	for(int i=0;i<n;i++){
		while(m>1 && cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
		ch[m++]=p[i];
	}
	int k=m;
	for(int i=n-2;i>=0;i--){
		while(m>k && cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
		ch[m++]=p[i];
	}
	if(n>1) m--;
	return m;
} 
 

int main(){
	cin>>n;
	cout<<"INTERSECTING LINES OUTPUT"<<endl;
	rep(i,0,n){
		Line l1,l2;
		cin>>l1.e.x>>l1.e.y>>l1.s.x>>l1.s.y>>l2.e.x>>l2.e.y>>l2.s.x>>l2.s.y;
		Vector v1=l1.s-l1.e;
		Vector v2=l2.s-l2.e;
		if(dcmp(cross(v1,v2))==0) {
			Vector v3=l1.s-l2.e;
			if(dcmp(cross(v1,v3))==0) cout<<"LINE"<<endl;
			else cout<<"NONE"<<endl;
			continue;
		}
		Point in=getinter(l1,l2);
		cout<<"POINT "<<fixed<<setprecision(2)<<in.x<<" "<<in.y<<endl;
		
	} 
	cout<<"END OF OUTPUT"<<endl;
}

收获与反思

  • 第一次接触计算几何，模板积累。