競プロ典型 009

https://atcoder.jp/contests/typical90/tasks/typical90_i

1点と取って、その点と残りの点を結ぶベクトルとx軸がなす角度を計算します。そのとき、角度でソートします。そうすると、しゃくとり法的に対角の点を求めることができて、そのうち角度が最大のものを求めます。ソートにかかる計算量が、しゃくとり法がです。がそれを全ての点について行います。そうすると、計算量はとなります。

// Three Point Angle
#![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()
}


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

type Point = (i32, i32);

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

fn calc_angle(pt: &Point, pt0: &Point) -> f64 {
    let pi = std::f64::consts::PI;
    let dy = (pt.1 - pt0.1) as f64;
    let dx = (pt.0 - pt0.0) as f64;
    let angle = f64::atan2(dy, dx) * 180.0 / pi;
    if angle >= 0.0 {
        angle
    }
    else {
        angle + 360.0
    }
}


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

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

// angle1 to angle2
fn diff_angle(angle1: f64, angle2: f64) -> f64 {
    if angle1 < angle2 {
        angle2 - angle1
    }
    else {
        360.0 - angle2 + angle1
    }
}

fn abs_angle(angle1: f64, angle2: f64) -> f64 {
    let a = diff_angle(angle1, angle2);
    if a <= 180.0 {
        a
    }
    else {
        360.0 - a
    }
}

fn prev_index(j: usize, N: usize) -> usize {
    if j > 0 { j - 1 } else { N - 1 }
}

fn next_index(j: usize, N: usize) -> usize {
    if j < N - 1 { j + 1 } else { 0 }
}

fn max_angle(pt0: &Point, points: &Vec<Point>) -> f64 {
    let mut angles: Vec<f64> = points.iter().filter(|&&pt| pt != *pt0).
                                map(|pt| calc_angle(pt, pt0)).collect();
    angles.sort_by(|a, b| a.partial_cmp(b).unwrap());
    let N = angles.len();
    let mut max_angle: f64 = 0.0;
    let mut i: usize = 0;
    let mut j2: usize = 1;
    while i < N {
        if diff_angle(angles[i], angles[j2]) <= 180.0 {
            j2 = next_index(j2, N)
        }
        else {
            let j1 = prev_index(j2, N);
            max_angle = max_angle.max(abs_angle(angles[i], angles[j1]).max(
                                           abs_angle(angles[i], angles[j2])));
            i += 1
        }
    }
    max_angle
}

fn F(points: Vec<Point>) -> f64 {
    points.iter().map(|pt1| max_angle(pt1, &points)).
                max_by(|a, b| a.partial_cmp(b).unwrap()).unwrap()
}

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