// compile: make data // run: time ./data < big.in > big.out && diff big.out big.ans #include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #ifdef LOCAL #include <debug/codeforces.h> #define debug(x...) _debug_print(#x, x); #define Debug(x...) _debug_print_format(#x, x); std::ifstream terminal("/dev/tty"); #define PP cerr<<"\033[1;30mpause...\e[0m",terminal.ignore(); #else #define debug(x...) #define Debug(x...) #define PP #endif template<typename...Args> void print_(Args...args){((cout<<args<<" "),...)<<endl;} #define VI vector<int> #define VII vector<vector<int>> #define VIII vector<vector<vector<int>>> #define rep(i,a,b) for(int i=(a);i<(int)(b);++i) #define sz(v) ((int)(v).size()) #define print(...) print_(__VA_ARGS__); #define FIND(a, x) ((find(a.begin(),a.end(),(x))!=a.end())?1:0) #define cmin(x,...) x=min({(x), __VA_ARGS__}) #define cmax(x,...) x=max({(x), __VA_ARGS__}) #define INTMAX (int)(9223372036854775807) #define INF (int)(1152921504606846976) #define NaN (int)(0x8b88e1d0595d51d1) #define double long double #define int long long #define uint unsigned long long #define MAXN 200010 template <typename T> struct point2d { T x, y; point2d() {} point2d(int X, int Y): x(X), y(Y) {} point2d<T> operator+(const point2d<T> &rhs) const { point2d<T> res(x + rhs.x, y + rhs.y); return res; } point2d<T> operator-(const point2d<T> &rhs) const { point2d<T> res(x - rhs.x, y - rhs.y); return res; } bool operator==(const point2d<T> &rhs) const { return x == rhs.x && y == rhs.y; } T dot(const point2d<T> &rhs) const { return x * rhs.x + y * rhs.y; } T cross2(const point2d<T> &rhs) const { return x * rhs.y - y * rhs.x; } double norm() const { return sqrt(x * x + y * y); } }; template <typename T> struct line2d { point2d<T> a, b; line2d() {} line2d(point2d<T> A, point2d<T> B): a(A), b(B) {} bool on(point2d<T> p, bool ica = 1, bool icb = 1) { if (!ica && a == p) return false; if (!icb && b == p) return false; point2d<T> v1 = p - a, v2 = p - b; return v1.cross2(v2) == 0 && v1.dot(v2) <= 0; } bool intersect(line2d<T> &rhs, bool ica = 1, bool icb = 1) { line2d<T> &lhs = *this; if (!ica && rhs.on(lhs.a)) return false; if (!icb && rhs.on(lhs.b)) return false; if (lhs.on(rhs.a, ica, icb) || lhs.on(rhs.b, ica, icb)) return true; if ((ica && rhs.on(lhs.a)) || (icb && rhs.on(lhs.b))) return true; auto mul = [](T A, T B) -> T { if (A == 0 || B == 0) return 0; if ((A > 0 && B > 0) || (A < 0 && B < 0)) return 1; return -1; }; point2d<T> ab = lhs.b - lhs.a; point2d<T> ac = rhs.a - lhs.a; point2d<T> ad = rhs.b - lhs.a; point2d<T> cd = rhs.b - rhs.a; point2d<T> ca = lhs.a - rhs.a; point2d<T> cb = lhs.b - rhs.a; if (mul(ab.cross2(ac), ab.cross2(ad)) < 0 && mul(cd.cross2(ca), cd.cross2(cb)) < 0) return true; return false; } }; void solve() { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; line2d<int> l1(point2d<int>(x1, y1), point2d<int>(x2, y2)); cin >> x1 >> y1 >> x2 >> y2; line2d<int> l2(point2d<int>(x1, y1), point2d<int>(x2, y2)); cout << (l1.intersect(l2) ? "YES" : "NO") << endl; } int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int _; cin >> _; while (_--) solve(); return 0; }
No Comments