| Task: | Line Segment Intersection |
| Sender: | aalto26jh_007 |
| Submission time: | 2026-11-09 15:05:25 +0200 |
| Language: | C++ (C++20) |
| Status: | READY |
| Result: | WRONG ANSWER |
| test | verdict | time | |
|---|---|---|---|
| #1 | ACCEPTED | 0.18 s | details |
| #2 | ACCEPTED | 0.23 s | details |
| #3 | ACCEPTED | 0.33 s | details |
| #4 | WRONG ANSWER | 0.43 s | details |
| #5 | ACCEPTED | 0.00 s | details |
| #6 | ACCEPTED | 0.00 s | details |
Code
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#include <bits/stdc++.h>
using namespace std;
bool doIntersect(int p1[], int q1[], int p2[], int q2[])
{
// Equation of line 1:
// a1*x + b1*y = c1
long long a1 = q1[1] - p1[1];
long long b1 = p1[0] - q1[0];
long long c1 = a1 * p1[0] + b1 * p1[1];
// Equation of line 2:
// a2*x + b2*y = c2
long long a2 = q2[1] - p2[1];
long long b2 = p2[0] - q2[0];
long long c2 = a2 * p2[0] + b2 * p2[1];
// Determinant of the two line equations.
// If it is 0, the lines are parallel or collinear.
long long det = a1 * b2 - a2 * b1;
// Handle parallel or collinear lines.
if (det == 0)
{
// The lines are parallel but different.
if (a1 * p2[0] + b1 * p2[1] != c1)
return false;
// The lines are collinear.
// Check whether their bounding boxes overlap.
return !(max(p1[0], q1[0]) < min(p2[0], q2[0]) || max(p2[0], q2[0]) < min(p1[0], q1[0]) ||
max(p1[1], q1[1]) < min(p2[1], q2[1]) || max(p2[1], q2[1]) < min(p1[1], q1[1]));
}
// Calculate the numerator of the intersection point.
// x = xNum / det
// y = yNum / det
long long xNum = b2 * c1 - b1 * c2;
long long yNum = a1 * c2 - a2 * c1;
// Find the bounding box of the first segment.
long long minX1 = min(p1[0], q1[0]);
long long maxX1 = max(p1[0], q1[0]);
long long minY1 = min(p1[1], q1[1]);
long long maxY1 = max(p1[1], q1[1]);
// Find the bounding box of the second segment.
long long minX2 = min(p2[0], q2[0]);
long long maxX2 = max(p2[0], q2[0]);
long long minY2 = min(p2[1], q2[1]);
long long maxY2 = max(p2[1], q2[1]);
// Make the denominator positive so that
// all comparisons below use the same direction.
if (det < 0)
{
det = -det;
xNum = -xNum;
yNum = -yNum;
}
// Check whether the intersection point lies
// inside both line segments.
return xNum >= minX1 * det && xNum <= maxX1 * det && yNum >= minY1 * det && yNum <= maxY1 * det &&
xNum >= minX2 * det && xNum <= maxX2 * det && yNum >= minY2 * det && yNum <= maxY2 * det;
}
int main()
{
int p1[] = {0, 0};
int q1[] = {0, 0};
int p2[] = {0, 0};
int q2[] = {0, 0};
int n_checks;
cin >> n_checks;
string ans = "";
for(int i = 0; i < n_checks; ++i)
{
cin >> p1[0] >> p1[1];
cin >> q1[0] >> q1[1];
cin >> p2[0] >> p2[1];
cin >> q2[0] >> q2[1];
bool res = doIntersect(p1, q1, p2, q2);
ans += res ? "YES\n" : "NO\n";
}
cout << ans;
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 ... |
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 ... |
Test 3
Verdict: ACCEPTED
| input |
|---|
| 100000 492853 -452834 -657156 -282543... |
| correct output |
|---|
| YES YES NO YES YES ... |
| user output |
|---|
| YES YES NO YES YES ... |
Test 4
Verdict: WRONG ANSWER
| input |
|---|
| 100000 788522666 939776556 -831492125... |
| correct output |
|---|
| NO NO NO NO NO ... |
| user output |
|---|
| NO NO NO NO NO ... |
Feedback: Incorrect character on line 11 col 1: expected "YES", got "NO"
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 |
