CSES - Aalto Competitive Programming 2024 - wk10 - Homework - Results
Submission details
Task:Line Segment Intersection
Sender:snude
Submission time:2024-11-08 09:32:42 +0200
Language:C++ (C++11)
Status:READY
Result:
Test results
testverdicttime
#10.07 sdetails
#20.08 sdetails
#30.10 sdetails
#40.12 sdetails
#5ACCEPTED0.00 sdetails
#60.00 sdetails

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// Debug printing
#ifdef DEBUG
#define deb(fmt, args...) printf("DEBUG: %d: " fmt, __LINE__, ##args)
#define debug_print(fmt, args...) printf(fmt, ##args)
#else
#define deb(fmt, args...)
#define debug_print(fmt, args...)
#endif
void print_array(vector<int> in, const string title = "Vector")
{
debug_print("DEBUG: %s [\nDEBUG: ", title.c_str());
for (unsigned int i = 0; i < in.size(); i++) {
debug_print("%d ", in[i]);
}
debug_print("\nDEBUG: ] END\n");
}
void print_matrix(vector<vector<int> > in, const string title = "Matrix")
{
debug_print("DEBUG: %s [\nDEBUG: ", title.c_str());
for (unsigned int i = 0; i < in.size(); i++) {
for (unsigned int j = 0; j < in[i].size(); j++) {
debug_print("%d ", in[i][j]);
}
debug_print("\nDEBUG: ");
}
debug_print("DEBUG: ] END\n");
}
int main(int argc, char *argv[])
{
ios::sync_with_stdio(0);
cin.tie(0);
// Read the input parameters
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x1, y1, x2, y2;
int x3, y3, x4, y4;
cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
// Check if there are shared endpoints.
if ((x1 == x3 && y1 == y3) || (x1 == x4 && y1 == y4) ||
(x2 == x3 && y2 == y3) || (x2 == y4 && x2 == y4)) {
cout << "YES\n";
continue;
}
// Line segments are on the same line
int vx1, vy1, vx2, vy2;
vx1 = x2 - x1;
vy1 = y2 - y2;
vx2 = x4 - x3;
vy2 = y4 - y3;
int cross = vx1 * vy2 - vx2 - vy1;
if (cross == 0 && ((x3 >= x1 && x3 <= x2) || (x4 >= x1 && x4 <= x2)))
{
cout << "YES\n";
continue;
} else {
int dx1, dy1, dx2, dy2;
dx1 = x3 - x1;
dy1 = y3 - y1;
dx2 = x3 - x2;
dy2 = y3 - y2;
int d = abs(dx1 * dy2 - dx2 * dy1) / 2;
if ((cross > 0 && d <= 0) || (cross < 0 && d >= 0)) {
cout << "YES\n";
continue;
}
}
cout << "NO\n";
}
}

Test details

Test 1

Verdict:

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
YES
YES
NO
NO
NO
...
Truncated

Test 2

Verdict:

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

correct output
NO
NO
YES
NO
YES
...

user output
YES
YES
NO
YES
YES
...
Truncated

Test 3

Verdict:

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

correct output
YES
YES
NO
YES
YES
...

user output
YES
NO
NO
YES
NO
...
Truncated

Test 4

Verdict:

input
100000
788522666 939776556 -831492125...

correct output
NO
NO
NO
NO
NO
...

user output
NO
YES
NO
YES
YES
...
Truncated

Test 5

Verdict: ACCEPTED

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

correct output
YES

user output
YES

Test 6

Verdict:

input
1
-1000000000 1000000000 9999999...

correct output
NO

user output
YES