Question A: intersecting line segments - structure

Question A: intersecting line segments - structure

Time limit: 1 Sec memory limit: 128 MB
Submitted by: 477 solved by: 158
[Submission][state][Discussion Edition]

Title Description

Each line segment is described by two points on the plane. For two arbitrary input line segments, the structure is used to judge whether they intersect.

Tip: the slope of straight line between two points (x1,y1), (x2,y2) is k=(y2-y1)/(x2-x1)

input

Judge times and x1, y1, x2, y2 of 2 line segments

output

Intersect

sample input

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

sample output

disjoint

intersect

disjoint


See the blog for the analysis of line intersection principle. It is recommended to understand the principle carefully before taking the code
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;
    //Vector from point A to point B
    v.x=B.x-A.x;
    v.y=B.y-A.y;
    return v;
}
 
double Cross_product(Vector a,Vector b){
//Finding the cross product of a vector
    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){
    //Judge whether two rectangles cross each other
    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);
    //Return 0 does not hold at the same time, two rectangles repel each other
}
 
 
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;//Repel each other, return directly, line segments do not intersect
    } 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;//intersect
        } else{
            return 0;
        }
    }
 
}
 
//Three structures need to be created
//   Structure of point
//   Structure of vector
//   Rectangular structure
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;
}

 

Posted on Wed, 04 Dec 2019 09:40:47 -0800 by moallam