POJ 1410 Intersection （线段与线段相交）

题意：判断线段与实心矩形是否有公共点。

题解：线段与线段相交
注意两点：
①矩形给出的坐标要重新判断。
②矩形实心。

#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;
    }
    //点积
    double operator *(const Point& b)const {
        return x * b.x + y * b.y;
    }
};

//LINE
struct Line {
    Point s, e;
    Line() {}
    Line(Point _s, Point _e) {
        s = _s;
        e = _e;
    }
    //两线段相交判断
    //2 规范相交
    //1 非规范相交
    //0 不相交
    int segcrossseg(Line v) {
        int d1 = sgn((e - s) ^ (v.s - s));
        int d2 = sgn((e - s) ^ (v.e - s));
        int d3 = sgn((v.e - v.s) ^ (s - v.s));
        int d4 = sgn((v.e - v.s) ^ (e - v.s));
        if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2)return 2;
        return (d1 == 0 && sgn((v.s - s) * (v.s - e)) <= 0) ||
            (d2 == 0 && sgn((v.e - s) * (v.e - e)) <= 0) ||
            (d3 == 0 && sgn((s - v.s) * (s - v.e)) <= 0) ||
            (d4 == 0 && sgn((e - v.s) * (e - v.e)) <= 0);
    }
};

int n, xa, ya, xb, yb, xl, yl, xr, yr;
int main() {
    scanf("%d", &n);
    while (n--) {
        scanf("%d%d%d%d%d%d%d%d", &xa, &ya, &xb, &yb, &xl, &yl, &xr, &yr);
        if (xl > xr) swap(xl, xr);
        if (yl < yr) swap(yl, yr);
        Line l[4];
        l[0] = Line(Point(xl, yl), Point(xr, yl));
        l[1] = Line(Point(xl, yl), Point(xl, yr));
        l[2] = Line(Point(xr, yl), Point(xr, yr));
        l[3] = Line(Point(xl, yr), Point(xr, yr));
        Line temp = Line(Point(xa, ya), Point(xb, yb));
        int flag = 0;
        for (int i = 0; i < 4; i++) {
            if (temp.segcrossseg(l[i])) {
                flag = 1;
                break;
            }
        }
        if (xa >= xl && xa <= xr && ya <= yl && ya >= yr) flag = 1;
        if (xb >= xl && xb <= xr && yb <= yl && yb >= yr) flag = 1;
        if (flag) puts("T");
        else puts("F");
    }
    return 0;
}

最后

以上就是懵懂泥猴桃为你收集整理的POJ 1410 Intersection （线段与线段相交）的全部内容，希望文章能够帮你解决POJ 1410 Intersection （线段与线段相交）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。