Untitled
unknown
plain_text
19 days ago
1.2 kB
4
Indexable
Never
#include <bits/stdc++.h> using namespace std; struct Point { int x, y; }; int checkOrientation(Point a, Point b, Point c) { int res = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y); return (res == 0) ? 0 : (res > 0) ? 1 : 2; } bool onSegment(Point a, Point b, Point c) { return b.x <= max(a.x, c.x) && b.x >= min(a.x, c.x) && b.y <= max(a.y, c.y) && b.y >= min(a.y, c.y); } bool checkIntersection(Point p1, Point q1, Point p2, Point q2) { int o1 = checkOrientation(p1, q1, p2); int o2 = checkOrientation(p1, q1, q2); int o3 = checkOrientation(p2, q2, p1); int o4 = checkOrientation(p2, q2, q1); if (o1 != o2 && o3 != o4) return true; if (o1 == 0 && onSegment(p1, p2, q1)) return true; if (o2 == 0 && onSegment(p1, q2, q1)) return true; if (o3 == 0 && onSegment(p2, p1, q2)) return true; if (o4 == 0 && onSegment(p2, q1, q2)) return true; return false; } int main() { int t; cin >> t; while (t--) { Point p1, q1, p2, q2; cin >> p1.x >> p1.y >> q1.x >> q1.y >> p2.x >> p2.y >> q2.x >> q2.y; cout << (checkIntersection(p1, q1, p2, q2) ? "YES" : "NO") << endl; } return 0; }
Leave a Comment