# 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

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

disjoint

intersect

disjoint

## See the blog for the analysis of line intersection principle. It is recommended to understand the principle carefully before taking the codehttps://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);

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