| Task: | Line Segment Intersection |
| Sender: | aalto26jh_007 |
| Submission time: | 2026-11-11 15:59:23 +0200 |
| Language: | C++ (C++20) |
| Status: | READY |
| Result: | WRONG ANSWER |
| test | verdict | time | |
|---|---|---|---|
| #1 | ACCEPTED | 0.19 s | details |
| #2 | ACCEPTED | 0.25 s | details |
| #3 | WRONG ANSWER | 0.35 s | details |
| #4 | WRONG ANSWER | 0.44 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(vector<int> a, vector<int> b, vector<int> c, vector<int> d)
{
if(a == c || a == d || b == c || b == d) return true;
int cross_prod_ab_c = (c[0] - a[0]) * (c[1] - b[1]) - (c[1] - a[1]) * (c[0] - b[0]);
int cross_prod_ab_d = (d[0] - a[0]) * (d[1] - b[1]) - (d[1] - a[1]) * (d[0] - b[0]);
int cross_prod_cd_a = (a[0] - c[0]) * (a[1] - d[1]) - (a[1] - c[1]) * (a[0] - d[0]);
int cross_prod_cd_b = (b[0] - c[0]) * (b[1] - d[1]) - (b[1] - c[1]) * (b[0] - d[0]);
if(((cross_prod_ab_c > 0 && cross_prod_ab_d < 0) || (cross_prod_ab_c < 0 && cross_prod_ab_d > 0)) &&
((cross_prod_cd_a > 0 && cross_prod_cd_b < 0) || (cross_prod_cd_a < 0 && cross_prod_cd_b > 0)))
return true;
if(cross_prod_ab_c == 0 &&
min(a[0], b[0]) <= c[0] && c[0] <= max(a[0], b[0]) &&
min(a[1], b[1]) <= c[1] && c[1] <= max(a[1], b[1])) return true;
if(cross_prod_ab_d == 0 &&
min(a[0], b[0]) <= d[0] && d[0] <= max(a[0], b[0]) &&
min(a[1], b[1]) <= d[1] && d[1] <= max(a[1], b[1])) return true;
if(cross_prod_cd_a == 0 &&
min(c[0], d[0]) <= a[0] && a[0] <= max(c[0], d[0]) &&
min(c[1], d[1]) <= a[1] && a[1] <= max(c[1], d[1])) return true;
if(cross_prod_cd_b == 0 &&
min(c[0], d[0]) <= b[0] && b[0] <= max(c[0], d[0]) &&
min(c[1], d[1]) <= b[1] && b[1] <= max(c[1], d[1])) return true;
return false;
}
int main()
{
vector<int> p1 = {0, 0};
vector<int> q1 = {0, 0};
vector<int> p2 = {0, 0};
vector<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: WRONG ANSWER
| input |
|---|
| 100000 492853 -452834 -657156 -282543... |
| correct output |
|---|
| YES YES NO YES YES ... |
| user output |
|---|
| NO YES NO NO NO ... |
Feedback: Incorrect character on line 1 col 1: expected "YES", got "NO"
Test 4
Verdict: WRONG ANSWER
| input |
|---|
| 100000 788522666 939776556 -831492125... |
| correct output |
|---|
| NO NO NO NO NO ... |
| user output |
|---|
| YES YES NO NO NO ... |
Feedback: Incorrect character on line 1 col 1: expected "NO", got "YES"
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 |
