CSES - Aalto Competitive Programming 2024 - wk10 - Homework - Results
Submission details
Task:Line Segment Intersection
Sender:arnxxau
Submission time:2024-11-10 17:41:20 +0200
Language:C++ (C++20)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.36 sdetails
#2ACCEPTED0.35 sdetails
#3ACCEPTED0.45 sdetails
#4ACCEPTED0.53 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails

Code

#include <iostream>
using namespace std;
struct Point {
long long x, y;
};
// Function to find the orientation of the triplet (p, q, r).
// 0 -> p, q and r are collinear
// 1 -> Clockwise
// 2 -> Counterclockwise
int orientation(Point p, Point q, Point r) {
long long val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
if (val == 0) return 0; // Collinear
return (val > 0) ? 1 : 2; // Clock or counterclockwise
}
// Check if point q lies on segment pr
bool onSegment(Point p, Point q, Point r) {
if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
return true;
return false;
}
// Returns true if line segment 'p1q1' and 'p2q2' intersect.
bool doIntersect(Point p1, Point q1, Point p2, Point q2) {
// Find the four orientations needed for the general and special cases
int o1 = orientation(p1, q1, p2);
int o2 = orientation(p1, q1, q2);
int o3 = orientation(p2, q2, p1);
int o4 = orientation(p2, q2, q1);
// General case
if (o1 != o2 && o3 != o4)
return true;
// Special Cases
// p1, q1 and p2 are collinear and p2 lies on segment p1q1
if (o1 == 0 && onSegment(p1, p2, q1)) return true;
// p1, q1 and q2 are collinear and q2 lies on segment p1q1
if (o2 == 0 && onSegment(p1, q2, q1)) return true;
// p2, q2 and p1 are collinear and p1 lies on segment p2q2
if (o3 == 0 && onSegment(p2, p1, q2)) return true;
// p2, q2 and q1 are collinear and q1 lies on segment p2q2
if (o4 == 0 && onSegment(p2, q1, q2)) return true;
return false; // Doesn't fall in any of the above cases
}
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;
if (doIntersect(p1, q1, p2, q2))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
100000
9 7 1 8 8 -5 0 2
10 1 -1 2 -4 1 -7 3
10 2 -8 6 1 2 2 -1
-10 1 9 -7 4 -3 -5 0
...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...
Truncated

Test 2

Verdict: ACCEPTED

input
100000
81 745 -967 768 -451 -490 -454...

correct output
NO
NO
YES
NO
YES
...

user output
NO
NO
YES
NO
YES
...
Truncated

Test 3

Verdict: ACCEPTED

input
100000
492853 -452834 -657156 -282543...

correct output
YES
YES
NO
YES
YES
...

user output
YES
YES
NO
YES
YES
...
Truncated

Test 4

Verdict: ACCEPTED

input
100000
788522666 939776556 -831492125...

correct output
NO
NO
NO
NO
NO
...

user output
NO
NO
NO
NO
NO
...
Truncated

Test 5

Verdict: ACCEPTED

input
1
1 6 6 6 4 4 1000000000 1000000...

correct output
YES

user output
YES

Test 6

Verdict: ACCEPTED

input
1
-1000000000 1000000000 9999999...

correct output
NO

user output
NO