アルゴリズムと数学 037

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ah

なかなか通らなくて、仕方なくPythonで書いたらあっさり通って、それをまねしてみた。
2つの線分が平行なら、4点が同一直線上になければならなくて、それを射影して領域が重なっていなければならない。そうでなければ2つの直線に交点があって、それが両方の線分上になければならない。

// Intersection
#![allow(non_snake_case)]

use std::ops::Sub;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

fn YesNo(b: bool) -> String {
    return if b { "Yes".to_string() } else { "No".to_string() }
}


//////////////////// Point ////////////////////

#[derive(Clone, Copy)]
#[derive(Debug)]
struct Point {
    x: i64,
    y: i64,
}

impl Sub for Point {
    type Output = Self;
    
    fn sub(self, other: Self) -> Self {
        Self { x: self.x - other.x, y: self.y - other.y }
    }
}

impl Point {
    fn read() -> Point {
        let v = read_vec();
        Point { x: v[0], y: v[1] }
    }
    
    fn inner_product(v: &Point, w: &Point) -> i64 {
        v.x * w.x + v.y * w.y
    }
}


//////////////////// Fraction ////////////////////

#[derive(Clone, Copy)]
#[derive(Debug)]
struct Fraction {
    num: i64,
    den: i64
}

impl Fraction {
    fn gcd(n: i64, m: i64) -> i64 {
        if m == 0 { n } else { Fraction::gcd(m, n % m) }
    }
    
    fn create(x: i64, y: i64) -> Fraction {
        let d = Fraction::gcd(x, y);
        let x1 = x / d;
        let y1 = y / d;
        if y1 > 0 {
            Fraction { num: x1, den: y1 }
        }
        else {
            Fraction { num: -x1, den: -y1 }
        }
    }
}


//////////////////// process ////////////////////

fn read_input() -> Vec<Point> {
    (0..4).map(|_| Point::read()).collect::<Vec<Point>>()
}

fn f(points: Vec<Point>) -> bool {
    let dir12 = points[1] - points[0];
    let dir34 = points[3] - points[2];
    let dir13 = points[2] - points[0];
    if dir12.x * dir34.y == dir12.y * dir34.x {     // parallel
        if dir12.x * dir13.y != dir12.y * dir13.x {     // 4点は同じ直線上でない
            return false
        }
        
        // points1を基準にどの位置にいるのか
        let dir14 = points[3] - points[0];
        let t1: i64 = 0;
        let t2 = Point::inner_product(&dir12, &dir12);
        let t3 = Point::inner_product(&dir13, &dir12);
        let t4 = Point::inner_product(&dir14, &dir12);
        t1 <= t3 && t3 <= t2 || t1 <= t4 && t4 <= t2 ||
        t2 <= t3 && t3 <= t1 || t2 <= t4 && t4 <= t1 ||
        t3 <= t1 && t1 <= t4 || t3 <= t2 && t2 <= t4 ||
        t4 <= t1 && t1 <= t3 || t4 <= t2 && t2 <= t3
    }
    else {
        let a = dir12.x;
        let b = -dir34.x;
        let c = dir12.y;
        let d = -dir34.y;
        let e = dir13.x;
        let f = dir13.y;
        let D = a * d - b * c;
        let s = Fraction::create(d * e - b * f, D);
        let t = Fraction::create(-c * e + a * f, D);
        0 <= s.num && s.num <= s.den && 0 <= t.num && t.num <= t.den
    }
}

fn main() {
    let points = read_input();
    println!("{}", YesNo(f(points)))
}