-
Notifications
You must be signed in to change notification settings - Fork 154
/
2190 - Line Segment Intersection.cpp
66 lines (57 loc) · 1.47 KB
/
2190 - Line Segment Intersection.cpp
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
/*
Problem Name: Line Segment Intersection
Problem Link: https://cses.fi/problemset/task/2190
Author: Sachin Srivastava (mrsac7)
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define P complex<int>
#define X real()
#define Y imag()
int cross(P a, P b, P c) {
P u = b - a;
P v = c - a;
return (conj(u)*v).Y;
}
bool comp(const P &a, const P &b) {
return (a.X == b.X) ? (a.Y < b.Y) : (a.X < b.X);
}
bool mid(P a, P b, P c) {
vector<P> v = {a, b, c};
sort(v.begin(), v.end(), comp);
return (v[1] == c);
}
int sgn(int x) {
return (x > 0) - (x < 0);
}
bool check(P a, P b, P c, P d) {
int cp1 = cross(a, b, c);
int cp2 = cross(a, b, d);
int cp3 = cross(c, d, a);
int cp4 = cross(c, d, b);
if (cp1 == 0 && mid(a, b, c)) return 1;
if (cp2 == 0 && mid(a, b, d)) return 1;
if (cp3 == 0 && mid(c, d, a)) return 1;
if (cp4 == 0 && mid(c, d, b)) return 1;
if (sgn(cp1) != sgn(cp2) && sgn(cp3) != sgn(cp4)) return 1;
return 0;
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r" , stdin);
freopen("output.txt", "w", stdout);
#endif
int t; cin>>t;
while (t--) {
int x, y;
P a, b, c, d;
cin >> x >> y; a = {x, y};
cin >> x >> y; b = {x, y};
cin >> x >> y; c = {x, y};
cin >> x >> y; d = {x, y};
cout << (check(a, b, c, d) ? "YES" : "NO") << endl;
}
}