欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 1269 Intersecting Lines (两直线位置关系+求交点)

程序员文章站 2022-03-30 09:01:28
...

题意:给出两直线位置,求是平行、重合还是有交点,若有交点,输出。

题解:两直线位置关系+求交点
套板子。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<map>
#include<sstream>
#include<iomanip>
#define ll long long
using namespace std;
const double eps = 1e-8;
const double inf = 1e20;
const double pi = acos(-1.0);
const int maxp = 1010;
//Compares a double to zero
int sgn(double x) {
    if (fabs(x) < eps) return 0;
    if (x < 0) return -1;
    else return 1;
}
//POINT
struct Point {
    double x, y;
    Point() {}
    Point(double _x, double _y) {
        x = _x;
        y = _y;
    }
    Point operator -(const Point& b)const {
        return Point(x - b.x, y - b.y);
    }
    //叉积
    double operator ^(const Point& b)const {
        return x * b.y - y * b.x;
    }
};
//LINE
struct Line {
    Point s, e;
    Line() {}
    Line(Point _s, Point _e) {
        s = _s;
        e = _e;
    }
    //点和直线关系
    //1 在左侧
    //2 在右侧
    //3 在直线上
    int relation(Point p) {
        int c = sgn((p - s) ^ (e - s));
        if (c < 0)return 1;
        else if (c > 0)return 2;
        else return 3;
    }
    //两向量平行 (对应直线平行或重合)
    bool parallel(Line v) {
        return sgn((e - s) ^ (v.e - v.s)) == 0;
    }
    //两直线关系
    //0 平行
    //1 重合
    //2 相交
    int linecrossline(Line v) {
        if ((*this).parallel(v))
            return v.relation(s) == 3;
        return 2;
    }
    //求两直线的交点
     //要保证两直线不平行或重合
    Point crosspoint(Line v) {
        double a1 = (v.e - v.s) ^ (s - v.s);
        double a2 = (v.e - v.s) ^ (e - v.s);
        return Point((s.x * a2 - e.x * a1) / (a2 - a1), (s.y * a2 - e.y * a1) / (a2 - a1));
    }
};
int n, xa, ya, xb, yb, xc, yc, xd, yd;
int main() {
	scanf("%d", &n);
    puts("INTERSECTING LINES OUTPUT");
	for (int i = 1; i <= n; i++) {
		scanf("%d%d%d%d%d%d%d%d", &xa, &ya, &xb, &yb, &xc, &yc, &xd, &yd);
        Line line = Line(Point(xa, ya), Point(xb, yb));
        Line line2 = Line(Point(xc, yc), Point(xd, yd));
        int temp = line.linecrossline(line2);
        if (temp == 0) puts("NONE");
        else if (temp == 1) puts("LINE");
        else {
            Point ans = line.crosspoint(line2);
            printf("POINT %.2f %.2f\n", ans.x, ans.y);
        }
	}
    puts("END OF OUTPUT");
	return 0;
}