Intersecting Lines POJ - 1269

Intersecting Lines

Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 22767 Accepted: 9502

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

思路：判断两直线的关系，运用叉乘判断两直线是否平行，当Cross(line_1,line_2)==0时，直线有重合和平行两种关系。
判断一下点C D是否在Line_1上。而当两直线一个交点时有如下公式直线Line_1有点（x1,y1）,(x2,y2) Line_2有点(x3,y3),(x4,y4).
证明可参考此篇博客

Ac Code:

#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<memory.h>
#include<cmath>
#include<vector>
#include<iomanip>
#define pii pair<int,int>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int Max = 1e5 + 5;


#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b))< EPS )

class Point
{
   
public:
	double x, y;
	Point(double x = 0, double y = 0) :x(x), y(y) {
   }
	Point operator + (Point p) {
    return Point(x + p.x, y + p.y); }
	Point operator - (Point p) {
    return Point(x - p.x, y - p.y); }
	Point operator * (double a) {
    return Point(a * x, a * y); }
	Point operator / (double a) {
    return Point(x / a, y / a); }

	double abs() {
    return sqrt(norm()); }
	double norm() {
    return x * x + y * y; }
	bool operator < (const Point& p)const
	{
   
		return x != p.x ? x < p.x : y < p.y;
	}
	bool operator == (const Point& p)const
	{
   
		return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS;
	}
};

typedef Point Vector;

struct Segment
{
   
	Point p1, p2;
	Segment(Point a, Point b) :p1(a), p2(b) {
   }
};
typedef Segment Line;

class Circle
{
   
public:
	Point c;
	double r;
	Circle(Point c = Point(), double r = 0.0) :c(c), r(r) {
   }
};

typedef vector<Point> Polygon;

double dot(Vector a, Vector b)//点乘，求投影
{
   
	return a.x * b.x + a.y * b.y;
}

double cross(Vector a, Vector b)//叉乘，求面积
{
   
	return a.x * b.y - a.y * b.x;
}

bool isOrthogonal(Vector a, Vector b)//判断向量AB是否垂直
{
   
	return equals(dot(a, b), 0.0);
}

bool isOrthogonal(Point a1, Point a2, Point b1, Point b2)
{
   
	return isOrthogonal(a1 - a2, b1 - b2);
}

bool isOrthogonal(Segment s1, Segment s2)
{
   
	return equals(dot(s1.p2 - s1.p1, s2.p2 - s2.p1), 0.0);
}

bool isParallel(Vector a, Vector b)
{
   
	return equals(cross(a, b), 0.0);
}

Point project(Segment s, Point p)//点在线段上的投影
{
   
	Vector base = s.p2 - s.p1;
	double r = dot(p - s.p1, base) / base.norm();
	return s.p1 + base * r;
}

Point reflect(Segment s, Point p)//映像
{
   
	return p + (project(s, p) - p) * 2.0;
}

double getDistance(Point a, Point b)//两点之间的距离
{
   
	return (a - b).abs();
}

double getDistanceLP(Line l, Point p)//点到直线的距离
{
   
	return abs(cross(l.p2 - l.p1, p - l.p1) / (l.p2 - l.p1).abs());
}

double getDistanceSP(Segment s, Point p)//点到线段的距离
{
   
	if (dot(s.p2 - s.p1, p - s.p1) < 0.0)return (p - s.p1).abs();
	if (dot(s.p1 - s.p2, p - s.p2) < 0.0)return (p - s.p2).abs();
	return getDistanceLP(s, p);
}

int ccw(Point p0, Point p1, Point p2)
{
   
	Vector a = p1 - p0;
	Vector b = p2 - p0;
	if (cross(a, b) > EPS)return 1;//直线p0-p2在直线p0-p1的逆时针方向；
	if (cross(a, b) < -EPS)return -1;//直线p0-p2在直线p0-p1的顺时针方向；
	if (dot(a, b) < -EPS)return 2;//p2在p0-p1的后方
	if (a.norm() < b.norm())return -2;//p2在p0-p1的前方
	return 0;//p2在p0-p1上
}

bool intersect(Point p1, Point p2, Point p3, Point p4)//线段p1p2与线段p3p4是否相交
{
   
	return (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 && ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0);
}

bool intersect(Segment s1, Segment s2)//判断线段s1、s2是否相交
{
   
	return intersect(s1.p1, s1.p2, s2.p1, s2.p2);
}

double getDistance(Segment s1, Segment s2)//两线段之间的距离
{
   
	if (intersect(s1, s2))return 0.0;
	return min(min(getDistanceSP(s1, s2.p1), getDistanceSP(s1, s2.p2)),
		min(getDistanceSP(s2, s1.p1), getDistanceSP(s2, s1.p2)));
}

Point getCrossPoint(Segment s1, Segment s2)//线段s1与线段s2的交点
{
   
	Vector base = s2.p2 - s2.p1;
	double d1 = abs(cross(base, s1.p1 - s2.p1));
	double d2 = abs(cross(base, s1.p2 - s2.p1));
	double t = d1 / (d1 + d2);
	return s1.p1 + (s1.p2 - s1.p1) * t;
}

pair<Point, Point> getCrossPoints(Circle c, Line l)//求圆与直线的交点
{
   
	Vector pr = project(l, c.c);
	Vector e = (l.p2 - l.p1) / (l.p2 - l.p1).abs();
	double base = sqrt(c.r * c.r - (pr - c.c).norm());
	return make_pair(pr + e * base, pr - e * base);
}

double arg(Vector p) {
    return atan2(p.y, p.x); }
Vector polar(double a, double r) {
    return Point(cos(r) * a, sin(r) * a); }

pair<Point, Point> getCrossPoints(Circle c1, Circle c2)//圆与圆的交点
{
   
	double d = (c1.c - c2.c).abs();
	double a = acos((c1.r * c1.r + d * d - c2.r * c2.r) / (2 * c1.r * d));
	double t = arg(c2.c - c1.c);
	return make_pair(c1.c + polar(c1.r, t + a), c1.c + polar(c1.r, t - a));
}

int contains(Polygon g, Point p)//内包 点在多边形内返回2，多边形上返回1，多边形外返回0
{
   
	int n = g.size();
	bool x = false;
	for (int i = 0;i < n;i++)
	{
   
		Point a = g[i] - p, b = g[(i + 1) % n] - p;
		if (abs(cross(a, b)) < EPS && dot(a, b) < EPS)return 1;
		if (a.y > b.y) swap(a, b);
		if (a.y < EPS && EPS<b.y && cross(a, b)>EPS)x = !x;
	}
	return (x ? 2 : 0);
}

Polygon andrewScan(Polygon s)//凸包
{
   
	Polygon u, l;
	if (s.size() < 3)return s;
	sort(s.begin(), s.end());
	//将x值最小的2个点添加至u
	u.push_back(s[0]);
	u.push_back(s[1]);
	//将x值最大的2个点添加至u
	l.push_back(s[s.size() - 1]);
	l.push_back(s[s.size() - 2]);

	//构建凸包上部
	for (int i = 2;i < s.size();i++)
	{
   
		for (int n = u.size();n >= 2 && ccw(u[n - 2], u[n - 1], s[i]) != -1;n--)
		{
   
			u.pop_back();
		}
		u.push_back(s[i]);
	}
	//构造凸包下部
	for (int i = s.size() - 3;i >= 0;i--)
	{
   
		for (int n = l.size();n >= 2 && ccw(l[n - 2], l[n - 1], s[i]) != -1;n--)
		{
   
			l.pop_back();
		}
		l.push_back(s[i]);
	}
	//按顺时针方向生成凸包的点的序列
	reverse(l.begin(), l.end());
	for (int i = u.size() - 2;i >= 1;i--)
	{
   
		l.push_back(u[i]);
	}
	return l;
}

double xx, yy;

int getLineCross(Point a, Point b, Point c, Point d)
{
   
	if (isParallel(a - b, c - d))
	{
   
		if (ccw(a, b, c) != 1 && ccw(a, b, c) != -1 && ccw(a, b, d) != 1 && ccw(a, b, d) != -1) return 1;//两直线重叠
		else return 2; //两直线平行
	}
	xx = ((c.x - d.x) * (b.x * a.y - a.x * b.y) - (a.x - b.x) * (d.x * c.y - c.x * d.y)) / ((c.x - d.x) * (a.y - b.y) - (a.x - b.x) * (c.y - d.y));
	yy = ((c.y - d.y) * (b.y * a.x - a.y * b.x) - (a.y - b.y) * (d.y * c.x - c.y * d.x)) / ((c.y - d.y) * (a.x - b.x) - (a.y - b.y) * (c.x - d.x));
	return 3;//两直线相交
}
//y0 = ((y3-y4) * (y2*x1 - y1*x2) - (y1-y2) * (y4*x3 - y3*x4)) / ((y3-y4) * (x1-x2) - (y1-y2) * (x3-x4));
int main()
{
   
	FAST;
	int t;cin >> t;
	cout << "INTERSECTING LINES OUTPUT" << endl;
	while (t--)
	{
   
		Point a, b, c, d;
		cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y;
		int sec = getLineCross(a, b, c, d);
		if (sec == 1)cout << "LINE" << endl;
		if (sec == 2)cout << "NONE" <<endl;
		if (sec == 3)cout <<"POINT "<< fixed << setprecision(2) << xx << " " << yy << endl;
	}
	cout << "END OF OUTPUT" << endl;
}