AtCoder Beginner Contest 422 E

https://atcoder.jp/contests/abc422/tasks/abc422_e

過半数が一つの直線に乗っていれば、点をなるべく等分になるように2分割したとき少なくともどちらかが過半数が一つの直線に乗っています。例えば7点で4点直線に乗っていたとき、7点を4点と3点に分けますが、直線上の4点を(4, 0), (3, 1), (2, 2), (1, 3)のどれに分けてもどちらかの過半数になります。なので、これは分割統治法で解けます。
分割したときにどちらも同じ直線上に過半数の点が乗っていることがありうるので、そこだけは注意します。

// Colinear
#![allow(non_snake_case)]


//////////////////// 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 gcd<T>(a: T, b: T) -> T
where
    T: std::cmp::PartialEq + std::ops::Rem<Output = T> + Copy + Default,
{
    let mut a = a;
    let mut b = b;
    while b != T::default() {
        let t = b;
        b = a % b;
        a = t;
    }
    a
}


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

type Point = (i64, i64);

fn read_point() -> Point {
    let v: Vec<i64> = read_vec();
    (v[0], v[1])
}


//////////////////// Line ////////////////////

// ax + by + c = 0
type Line = (i64, i64, i64);

fn is_on_line(pt: &Point, line: &Line) -> bool {
    return line.0 * pt.0 + line.1 * pt.1 + line.2 == 0
}

fn create_line_by_two_points(pt1: &Point, pt2: &Point) -> Line {
    let dx = pt2.0 - pt1.0;
    let dy = pt2.1 - pt1.1;
    let d = gcd(dx, dy).abs();
    let c = dx * pt1.1 - dy * pt1.0;
    if dy > 0 {
        (dy/d, -dx/d, c/d)
    }
    else if dy < 0 {
        (-dy/d, dx/d, -c/d)
    }
    else if dx > 0 {
        (0, dx/d, -c/d)
    }
    else {
        (0, -dx/d, c/d)
    }
}

fn print_line(line: &Line) {
    println!("{} {} {}", line.0, line.1, line.2)
}


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

fn read_input() -> Vec<Point> {
    let N: usize = read();
    (0..N).map(|_| read_point()).collect::<Vec<_>>()
}

fn DC(points: &[Point]) -> Vec<(Line, usize)> {
    let N = points.len();
    if N == 2 {
        vec![(create_line_by_two_points(&points[0], &points[1]), 2)]
    }
    else if N == 3 {
        let line1 = create_line_by_two_points(&points[0], &points[1]);
        if is_on_line(&points[2], &line1) {
            vec![(line1, 3)]
        }
        else {
            let line2 = create_line_by_two_points(&points[0], &points[2]);
            let line3 = create_line_by_two_points(&points[1], &points[2]);
            vec![(line1, 2), (line2, 2), (line3, 2)]
        }
    }
    else {
        let mid = N / 2;
        let mut lines: Vec<(Line, usize)> = vec![];
        let v1 = DC(&points[..mid]);
        for &(line, n) in v1.iter() {
            let mut num = n;
            for pt in points[mid..].iter() {
                if is_on_line(pt, &line) {
                    num += 1
                }
            }
            if num * 2 > N {
                lines.push((line, num))
            }
        }
        let v2 = DC(&points[mid..]);
        for (line, n) in v2.iter() {
            if v1.iter().any(|&(line1, _)| line1 == *line) {
                continue
            }
            let mut num = *n;
            for pt in points[..mid].iter() {
                if is_on_line(&pt, &line) {
                    num += 1
                }
            }
            if num * 2 > N {
                lines.push((*line, num))
            }
        }
        lines
    }
}

fn F(points: Vec<Point>) {
    let lines = DC(&points[..]);
    if lines.is_empty() {
        println!("No")
    }
    else {
        println!("Yes");
        print_line(&lines[0].0)
    }
}

fn main() {
    let points = read_input();
    F(points)
}