結果

問題 No.2438 Double Least Square
ユーザー Jichou P (JichouP)Jichou P (JichouP)
提出日時 2023-08-19 21:35:38
言語 Rust
(1.77.0 + proconio)
結果
TLE  
実行時間 -
コード長 2,672 bytes
コンパイル時間 15,576 ms
コンパイル使用メモリ 400,116 KB
実行使用メモリ 15,816 KB
最終ジャッジ日時 2024-11-29 17:44:23
合計ジャッジ時間 78,119 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 77 ms
8,864 KB
testcase_01 AC 72 ms
8,868 KB
testcase_02 AC 131 ms
13,764 KB
testcase_03 AC 43 ms
8,736 KB
testcase_04 AC 43 ms
13,764 KB
testcase_05 AC 73 ms
8,864 KB
testcase_06 AC 30 ms
13,760 KB
testcase_07 AC 31 ms
8,740 KB
testcase_08 AC 84 ms
13,764 KB
testcase_09 AC 302 ms
8,740 KB
testcase_10 TLE -
testcase_11 TLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 TLE -
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 TLE -
testcase_26 TLE -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 TLE -
testcase_30 AC 75 ms
6,816 KB
testcase_31 AC 30 ms
6,816 KB
testcase_32 AC 141 ms
15,688 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

fn getline() -> String {
    let mut __ret = String::new();
    std::io::stdin().read_line(&mut __ret).ok();
    return __ret.trim_end().to_string();
}

struct Input {
    _n: usize,
    h: usize,
    p: Vec<(usize, usize)>,
}

fn input() -> Input {
    let n = getline().parse::<usize>().unwrap();
    let h = getline().parse::<usize>().unwrap();
    // let h = getline().parse::<usize>().unwrap();
    let mut p = Vec::new();
    for _ in 0..n {
        let s = getline();
        let v = s
            .split(' ')
            .map(|v| v.parse::<usize>().unwrap())
            .collect::<Vec<_>>();
        p.push((v[0], v[1]));
    }

    Input { _n: n, h, p }
}

fn l(Input { _n: _, h, p }: &Input, a1: f64, a2: f64) -> f64 {
    let f = |x: f64| a1 * x + (*h as f64);
    let g = |x: f64| a2 * x;

    p.iter()
        .map(|(xi, yi)| {
            let f_diff = ((*yi as f64) - f((*xi) as f64)).powi(2);
            let g_diff = ((*yi as f64) - g((*xi) as f64)).powi(2);
            f_diff.min(g_diff)
        })
        .sum()
}

fn newton(input: &Input, x: f64, y: f64) -> (f64, f64) {
    let l_x = (l(input, x + H, y) - l(input, x - H, y)) / (2.0 * H);
    let l_y = (l(input, x, y + H) - l(input, x, y - H)) / (2.0 * H);
    let l_xx = (l(input, x + H, y) - 2.0 * l(input, x, y) + l(input, x - H, y)) / (H.powi(2));
    let l_yy = (l(input, x, y + H) - 2.0 * l(input, x, y) + l(input, x, y - H)) / (H.powi(2));
    let l_xy = (l(input, x + H, y) + l(input, x - H, y) + l(input, x, y + H) + l(input, x, y - H)
        - 2.0 * l(input, x, y)
        - l(input, x + H, y + H)
        - l(input, x - H, y - H))
        / (2.0 * H.powi(2));
    let l_yx = l_xy;

    let k = l_xx * l_yy - l_xy * l_yx;
    if k == 0.0 {
        return (x, y);
    }
    let new_x = x - (1.0 / k) * (l_yy * l_x - l_xy * l_y);
    let new_y = y - (1.0 / k) * (-l_yx * l_x + l_xx * l_y);
    (new_x, new_y)
}

const H: f64 = 0.01;
const N: usize = 10;
const IN: usize = 2000;
const R: f64 = 10.0;

fn def_init_value(input: &Input) -> (f64, f64) {
    // let a = [[(0.0, 0.0); IN]; IN];
    let h = 2.0 * R / IN as f64;
    let (mut a1, mut a2, mut res) = (0.0, 0.0, 1000000.0);

    for i in 0..IN {
        for j in 0..IN {
            let tmp_a1 = -R + h * i as f64;
            let tmp_a2 = -R + h * j as f64;
            let tmp_res = l(input, tmp_a1, tmp_a2);
            if res > tmp_res {
                (a1, a2, res) = (tmp_a1, tmp_a2, tmp_res)
            }
        }
    }

    (a1, a2)
}

fn main() {
    let i = input();
    let (mut a1, mut a2) = def_init_value(&i);

    for _ in 0..N {
        (a1, a2) = newton(&i, a1, a2);
    }

    println!("{:?}", l(&i, a1, a2));
}
0