| Task: | Line Segment Intersection |
| Sender: | aalto26jh_033 |
| Submission time: | 2026-11-10 11:24:44 +0200 |
| Language: | C++ (C++20) |
| Status: | READY |
| Result: | ACCEPTED |
| test | verdict | time | |
|---|---|---|---|
| #1 | ACCEPTED | 0.08 s | details |
| #2 | ACCEPTED | 0.09 s | details |
| #3 | ACCEPTED | 0.10 s | details |
| #4 | ACCEPTED | 0.12 s | details |
| #5 | ACCEPTED | 0.00 s | details |
| #6 | ACCEPTED | 0.00 s | details |
Code
#include <bits/stdc++.h>
using namespace std;
// debug
template<class T> ostream& operator<<(ostream&, const vector<T>&);
template<class T> ostream& operator<<(ostream&, const set<T>&);
template<class T> ostream& operator<<(ostream&, const multiset<T>&);
template<class K, class V> ostream& operator<<(ostream&, const map<K, V>&);
template<class T, size_t N> ostream& operator<<(ostream&, const array<T, N>&);
template<class A, class B> ostream& operator<<(ostream& os, const pair<A, B>& p) { return os << "(" << p.first << ", " << p.second << ")"; }
template<class T>
void print_collection(ostream& os, const T& v) {
os << "{";
bool first = true;
for (const auto& x : v) {
if (!first) os << ", ";
first = false;
os << x;
}
os << "}";
}
template<class T> ostream& operator<<(ostream& os, const vector<T>& v) { print_collection(os, v); return os; }
template<class T> ostream& operator<<(ostream& os, const set<T>& v) { print_collection(os, v); return os; }
template<class T> ostream& operator<<(ostream& os, const multiset<T>& v) { print_collection(os, v); return os; }
template<class K, class V> ostream& operator<<(ostream& os, const map<K, V>& v) { print_collection(os, v); return os; }
template<class T, size_t N> ostream& operator<<(ostream& os, const array<T, N>& v) { print_collection(os, v); return os; }
#define dbg(x) cerr << #x << " = " << (x) << '\n'
using ll = long long;
constexpr int INF = 1'000'000'000; // 1e9
constexpr ll LINF = 1'000'000'000'000'000'000LL; // 1e18
constexpr int MOD = 1'000'000'007; // 1e9 + 7
inline ll add(ll a, ll b) { return (a + b) % MOD; }
inline ll sub(ll a, ll b) { return ((a - b) % MOD + MOD) % MOD; }
inline ll mul(ll a, ll b) { return (a * b) % MOD; }
typedef complex<ll> P;
#define X real()
#define Y imag()
ll crossProduct(P a, P b) {
return (conj(a)*b).Y;
}
// positive -> left; negative -> right; 0 -> on line
int pointLocation(P p, P s1, P s2) {
ll a = crossProduct(p-s1, p-s2);
return a == 0 ? 0 : (a>0 ? 1 : -1);
}
bool onSegment(P p, P s1, P s2) {
return pointLocation(p, s1, s2) == 0 && min(s1.X, s2.X) <= p.X && p.X <= max(s1.X, s2.X) && min(s1.Y, s2.Y) <= p.Y && p.Y <= max(s1.Y, s2.Y);
}
bool intersect(P a, P b, P c, P d) {
int pl1 = pointLocation(c, a, b), pl2 = pointLocation(d, a, b), pl3 = pointLocation(a, c, d), pl4 = pointLocation(b, c, d);
// case 1 or 2: same line or vertex contact
if (
(pl1 == 0 && onSegment(c, a, b)) ||
(pl2 == 0 && onSegment(d, a, b)) ||
(pl3 == 0 && onSegment(a, c, d)) ||
(pl4 == 0 && onSegment(b, c, d))
) return true;
// case 3: exactly one non vertex intersection
return pl1 != pl2 && pl3 != pl4;
}
void solve() {
int N;
cin >> N;
int x,y;
for(int i=0;i<N;++i) {
cin >> x >> y;
P p1 = {x,y};
cin >> x >> y;
P p2 = {x,y};
cin >> x >> y;
P p3 = {x,y};
cin >> x >> y;
P p4 = {x,y};
cout << (intersect(p1, p2, p3, p4) ? "YES" : "NO") << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
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: ACCEPTED
| input |
|---|
| 100000 788522666 939776556 -831492125... |
| correct output |
|---|
| NO NO NO NO NO ... |
| user output |
|---|
| NO NO NO NO 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 |
