| Task: | Line Segment Intersection |
| Sender: | aalto26jh_010 |
| Submission time: | 2026-11-06 14:34:18 +0200 |
| Language: | C++ (C++20) |
| Status: | READY |
| Result: | WRONG ANSWER |
| test | verdict | time | |
|---|---|---|---|
| #1 | WRONG ANSWER | 0.07 s | details |
| #2 | ACCEPTED | 0.08 s | details |
| #3 | ACCEPTED | 0.10 s | details |
| #4 | ACCEPTED | 0.12 s | details |
| #5 | WRONG ANSWER | 0.00 s | details |
| #6 | ACCEPTED | 0.00 s | details |
Code
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct Point {
long long x, y;
friend istream& operator>>(istream& in, Point& p) {
return in >> p.x >> p.y;
}
bool operator==(const Point & point) const {
return x == point.x && y == point.y;
}
};
static long long cross_product(const Point& a, const Point&b, const Point& c) {
return (b.x-a.x)*(c.y-b.y) - (c.x-b.x)*(b.y-a.y);
}
static bool intersects(const Point& a, const Point&b, const Point& c, const Point& d) {
const long long ab_c = cross_product(a, b, c);
const long long ab_d = cross_product(a, b, d);
// Same line
if (ab_c == 0 && ab_d == 0) {
if (max(min(a.x, b.x), min(c.x, d.x)) <= min(max(a.x, b.x), max(c.x, d.x)) &&
max(min(a.y, b.y), min(c.y, d.y)) <= min(max(a.y, b.y), max(c.y, d.y))) {
return true;
}
}
// Common vertex
if (a == c || a == d || b == c || b == d) {
return true;
}
const long long cd_a = cross_product(c, d, a);
const long long cd_b = cross_product(c, d, b);
// One intersection
return ((ab_c > 0 && ab_d < 0) || (ab_c < 0 && ab_d > 0)) &&
((cd_a > 0 && cd_b < 0) || (cd_a < 0 && cd_b > 0));
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
Point a, b, c, d;
cin >> a >> b >> c >> d;
cout << (intersects(a, b, c, d) ? "YES" : "NO") << '\n';
}
cout.flush();
return 0;
}
Test details
Test 1
Verdict: WRONG ANSWER
| 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 ... |
Feedback: Incorrect character on line 164 col 1: expected "YES", got "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: ACCEPTED
| input |
|---|
| 100000 788522666 939776556 -831492125... |
| correct output |
|---|
| NO NO NO NO NO ... |
| user output |
|---|
| NO NO NO NO NO ... |
Test 5
Verdict: WRONG ANSWER
| input |
|---|
| 1 1 6 6 6 4 4 1000000000 1000000... |
| correct output |
|---|
| YES |
| user output |
|---|
| NO |
Feedback: Incorrect character on line 1 col 1: expected "YES", got "NO"
Test 6
Verdict: ACCEPTED
| input |
|---|
| 1 -1000000000 1000000000 9999999... |
| correct output |
|---|
| NO |
| user output |
|---|
| NO |
