0%

CGL_2_B: Intersection

Intersection

For given two segments s1 and s2, print “1” if they are intersect, “0” otherwise.

s1 is formed by end points p0 and p1, and s2 is formed by end points p2 and p3.

Input

The entire input looks like:

1
2
3
4
5
q (the number of queries)
1st query
2nd query
...
qth query

Each query consists of integer coordinates of end points of s1 and s2 in the following format:

1
xp0 yp0 xp1 yp1 xp2 yp2 xp3 yp3

Output

For each query, print “1” or “0”.

Constraints

  • 1 ≤ q ≤ 1000
  • -10000 ≤ $x_{p_i},y_{p_i}$ ≤ 10000
  • p0≠p1 and p2≠p3.

Sample Input 1

1
2
3
4
3
0 0 3 0 1 1 2 -1
0 0 3 0 3 1 3 -1
0 0 3 0 3 -2 5 0

Sample Output 1

1
2
3
1
1
0

Source: https://onlinejudge.u-aizu.ac.jp/problems/CGL_2_B

判断两直线是否相交(包括不规范相交)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
struct Point{
double x,y;
Point(){}
Point(double x,double y):x(x),y(y){}
};
typedef Point Vector;
Vector operator + (Vector A,Vector B){
return Vector(A.x+B.x,A.y+B.y);
}
Vector operator - (Vector A,Vector B){
return Vector(A.x-B.x,A.y-B.y);
}
Vector operator * (Vector A,double p){
return Vector(A.x*p,A.y*p);
}
Vector operator / (Vector A,double p){
return Vector(A.x/p,A.y/p);
}
bool operator < (const Point& a,const Point& b){
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
const double eps = 1e-10;
int dcmp(double x){
if(fabs(x)<eps) return 0; else return (x<0?-1:1);
}
bool operator == (const Point& a,const Point& b){
return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0;
}
//点积
double Dot(Vector A,Vector B){
return A.x*B.x+A.y*B.y;
}
double Length(Vector A){
return sqrt(Dot(A,A));
}
double Angle(Vector A,Vector B){
return acos(Dot(A,B)/Length(A)/Length(B));
}

//叉积
double Cross(Vector A,Vector B){
return (A.x*B.y-A.y*B.x);
}
//三角形面积的二倍的叉乘公式
double Area2(Point A,Point B,Point C){
return Cross(B-A,C-A);
}
//向量旋转,rad是弧度
Vector Rotate(Vector A,double rad){
return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}
//计算向量的单位法线,先逆时针旋转90度,然后把长度归一化
Vector Normal(Vector A){
double Len=Length(A);
return Vector(-A.y/Len,A.x/Len);
}
//求两直线交点
//调用前请确保P+tv和Q+tw有唯一交点,当且仅当Cross(v,w)非0
Point GetLineIntersection(Point P,Vector v,Point Q,Vector w){
Vector u=P-Q;
double t=Cross(w,u)/Cross(v,w);
return P+v*t;
}
//点到直线的距离
double DistanceToLine(Point P,Point A,Point B){
Vector v1=B-A,v2=P-A;
return fabs(Cross(v1,v2))/Length(v1);
}
//点到线段的距离
double DistanceToSegment(Point P,Point A,Point B){
if(A==B) return Length(P-A);
Vector v1=B-A,v2=P-A,v3=P-B;
if(dcmp(Dot(v1,v2))<0) return Length(v2);
else if(dcmp(Dot(v1,v3))>0) return Length(v3);
else return fabs(Cross(v1,v2))/Length(v1);
}
//点在直线上的投影
Point GetLineProjection(Point P,Point A,Point B){
Vector v=B-A;
return A+v*(Dot(v,P-A)/Dot(v,v));
}
//反射
Point GetLineReflection(Point P,Point A,Point B){
return GetLineProjection(P,A,B)*2-P;
}
//判断两线段严格相交
bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2){
double c1=Cross(a2-a1,b1-a1), c2=Cross(a2-a1,b2-a1),
c3=Cross(b2-b1,a1-b1), c4=Cross(b2-b1,a2-b1);
return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0;
}
//判断点是否在线段上
bool OnSegment(Point P,Point a1,Point a2){
return dcmp(Cross(a1-P,a2-P))==0 && dcmp(Dot(a1-P,a2-P))<=0;
}
int main(){
int t;
cin>>t;
while(t--){
Point A,B,C,D;
cin>>A.x>>A.y>>B.x>>B.y>>C.x>>C.y>>D.x>>D.y;
bool ans1=SegmentProperIntersection(A,B,C,D);
bool ans2=OnSegment(A,C,D)||OnSegment(B,C,D)||OnSegment(C,A,B)||OnSegment(D,A,B);
if(ans1||ans2) cout<<1;
else cout<<0;
cout<<"\n";
}
return 0;
}