AtCoder ABC #139 F - Engines

問題

F - Engines

解説

公式解説結構長めに書いてあるけど実装としては

1. f64.atan2()で角度を求めてソート
2. 連続的に取りうる組み合わせを全て試す

これで で解ける

fn solve(xys: Vec<(i64, i64)>) -> f64 {
    let n = xys.len();
    let mut xys = xys;

    xys.sort_by(|&(x1, y1), &(x2, y2)| {
        let p1 = (y1 as f64).atan2(x1 as f64);
        let p2 = (y2 as f64).atan2(x2 as f64);

        p1.partial_cmp(&p2).unwrap()
    });

    let mut ans = 0.0;

    for i in 0..n {
        let mut x = 0;
        let mut y = 0;

        for j in 0..n {
            let k = (i + j) % n;
            let (ax, ay) = xys[k];
            x = x + ax;
            y = y + ay;

            let r = ((x * x + y * y) as f64).sqrt();
            if ans < r {
                ans = r;
            }

            if (i + j + 1) % n == i {
                break;
            }
        }
    }

    ans
}