Submission #2698755

---

Source Code Expand

use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n = read::<usize>();
    let mut seq = vec![(0, 0); n];
    for i in 0..n {
        let mut x = read::<i64>();
        let mut y = read::<i64>();
        if x > y {
            std::mem::swap(&mut x, &mut y);
        }
        seq[i] = (x, y);
    }
    let mut min_value = 1 << 32;
    let mut max_value = -(1 << 32);
    let mut que = vec![(0, 0); 3 * n];
    for i in 0..n {
        min_value = std::cmp::min(min_value, seq[i].0);
        max_value = std::cmp::max(max_value, seq[i].1);
        que[i * 3 + 0] = (-(1 << 32), seq[i].0);
        que[i * 3 + 1] = (seq[i].0, seq[i].1);
        que[i * 3 + 2] = (seq[i].1, 1 << 32);
    }
    que.sort();
    let mut ans = 1 << 61;
    let mut pos = 0;
    let mut right = -(1 << 32);
    for i in 0..3 * n {
        while pos < 3 * n && que[pos].0 < que[i].0 {
            right = std::cmp::max(right, que[pos].1);
            pos += 1;
        }
        if que[i].0 == -(1 << 32) || right == (1 << 32) {
            continue;
        }
        let lans = (max_value - min_value) * (right - que[i].0);
        assert!(lans >= 0);
        ans = std::cmp::min(ans, lans);
    }
    {
        let mut left = min_value;
        let mut right = max_value;
        for i in 0..n {
            left = std::cmp::max(left, seq[i].0);
            right = std::cmp::min(right, seq[i].1);
        }
        let lans = (left - min_value) * (max_value - right);
        assert!(lans >= 0);
        ans = std::cmp::min(ans, lans);
    }
    println!("{}", ans);
}

Submission Info

Judge Result