问题 A: 线段相交----结构体

时间限制: 1 Sec  内存限制: 128 MB
提交: 477  解决: 158
[提交][状态][讨论版]

题目描述

每个线段是用平面上的两个点来描述，用结构体实现对于任意输入的2个线段，判断其是否相交。

提示：两点(x1,y1), (x2,y2) 间直线斜率是k=(y2-y1)/(x2-x1).

输入

判断次数和2条线段的x1、y1、x2、y2

输出

是否相交

样例输入

3 1 5 2 9 1 3 2 4 5 6 7 8 5 7 7 7 2 5 1 0 9 4 2 9

样例输出

disjoint

intersect

disjoint

线段相交原理分析具体见博客，建议先仔细看懂原理之后再服用代码
https://www.cnblogs.com/shengshouzhaixing/archive/2013/03/17/2964950.html

#include <iostream>
using namespace std;
struct Point{
    double x;
    double y;
};
struct Vector{
    double x;
    double y;
};
struct MBR{
    double xmax;
    double xmin;
    double ymax;
    double ymin;
 
};
Vector Create_vector(Point A,Point B){
    Vector v;
    //从A点到B点的向量
    v.x=B.x-A.x;
    v.y=B.y-A.y;
    return v;
}
 
double Cross_product(Vector a,Vector b){
//求出向量的叉积
    return (a.x*b.y-a.y*b.x);
}
MBR Creat_mbr(Point A,Point B){
    MBR m;
    if (A.x>B.x) {
        m.xmin=B.x;
        m.xmax=A.x;
    } else{
        m.xmin=A.x;
        m.xmax=B.x;
    }
    if (A.y>B.y) {
        m.ymin=B.y;
        m.ymax=A.y;
    } else{
        m.ymax=B.y;
        m.ymin=A.y;
    }
    return m;
}
double MAX(int a,int b){
    if (a>b) {
        return a;
    } else{
        return b;
    }
}
double MIN(int a,int b){
    if (a>b) {
        return b;
    } else{
        return a;
    }
}
 
int MBR_cross(MBR m1,MBR m2){
    //判断两个矩形之间是否跨交
    double xmin,xmax,ymin,ymax;
    xmin=MAX(m1.xmin,m2.xmin);
    xmax=MIN(m1.xmax,m2.xmax);
 
    ymin=MAX(m1.ymin,m2.ymin);
    ymax=MIN(m1.ymax,m2.ymax);
    return (xmax>=xmin&&ymax>=ymin);
    //返回0 不同时成立，两个矩形相互排斥
}
 
 
int function(Point A,Point B,Point C,Point D){
 
    MBR m1=Creat_mbr(A,B);
    MBR m2=Creat_mbr(C,D);
 
    if (MBR_cross(m1,m2)==0) {
        return 0;//相互排斥，直接返回，线段不相交
    } else{
        Vector CA=Create_vector(C,A);
        Vector CB=Create_vector(C,B);
        Vector CD=Create_vector(C,D);
 
        Vector AC=Create_vector(A,C);
        Vector AB=Create_vector(A,B);
        Vector AD=Create_vector(A,D);
 
        if (Cross_product(CD,CA)*Cross_product(CD,CB)<=0 && Cross_product(AC,AB)*Cross_product(AD,AB)<=0 ) {
            return 1;//相交
        } else{
            return 0;
        }
    }
 
}
 
//需要创建三个结构体
//   点的结构体
//   向量的结构体
//   矩形的结构体
int main() {
    int t;
    cin>>t;
    while (t--) {
        Point A;
        Point B;
        Point C;
        Point D;
        cin>>A.x>>A.y;
        cin>>B.x>>B.y;
        cin>>C.x>>C.y;
        cin>>D.x>>D.y;
        if(function(A,B,C,D)){
            cout<<"intersect"<<endl;
        } else{
            cout<<"disjoint"<<endl;
        }
    }
    return 0;
}