Untitled

mail@pastecode.io avatar
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