Submission details
Task:Line Segment Intersection
Sender:aalto26jh_009
Submission time:2026-11-08 15:56:26 +0200
Language:Rust (2021)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.17 sdetails
#2ACCEPTED0.18 sdetails
#3ACCEPTED0.19 sdetails
#4ACCEPTED0.20 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails

Code

#![allow(unused)]

use std::collections::*;
use std::io;
use std::io::Read;

fn take_int() -> usize {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    return input.trim().parse::<usize>().unwrap();
}

fn cross(s1: (i64, i64), s2: (i64, i64), p: (i64, i64)) -> i64 {
    (p.0 - s1.0) * (p.1 - s2.1) - (p.0 - s2.0) * (p.1 - s1.1)
}

fn on_seg(a: (i64, i64), b: (i64, i64), p: (i64, i64)) -> bool {
    cross(a, b, p) == 0
        && a.0.min(b.0) <= p.0
        && p.0 <= a.0.max(b.0)
        && a.1.min(b.1) <= p.1
        && p.1 <= a.1.max(b.1)
}

fn intersection(a: (i64, i64), b: (i64, i64), c: (i64, i64), d: (i64, i64)) {
    // case 3
    let d1 = cross(a, b, c).signum();
    let d2 = cross(a, b, d).signum();
    let d3 = cross(c, d, a).signum();
    let d4 = cross(c, d, b).signum();
    if d1 * d2 < 0 && d3 * d4 < 0 {
        println!("YES");
        return;
    }

    // case 1 and 2
    if on_seg(a, b, c) || on_seg(a, b, d) || on_seg(c, d, a) || on_seg(c, d, b) {
        println!("YES");
        return;
    }
    println!("NO");
}

fn main() {
    let mut n = take_int();
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut it = input
        .trim()
        .split_whitespace()
        .map(|x| x.parse::<i64>().unwrap());

    for _ in 0..n {
        intersection(
            (it.next().unwrap(), it.next().unwrap()),
            (it.next().unwrap(), it.next().unwrap()),
            (it.next().unwrap(), it.next().unwrap()),
            (it.next().unwrap(), it.next().unwrap()),
        );
    }
}

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