結果
問題 | No.2012 Largest Triangle |
ユーザー |
![]() |
提出日時 | 2022-07-15 22:26:58 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 64 ms / 2,500 ms |
コード長 | 3,857 bytes |
コンパイル時間 | 16,334 ms |
コンパイル使用メモリ | 376,684 KB |
実行使用メモリ | 9,344 KB |
最終ジャッジ日時 | 2024-06-27 21:20:20 |
合計ジャッジ時間 | 17,091 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
コンパイルメッセージ
warning: unused import: `std::io::Write` --> src/main.rs:2:5 | 2 | use std::io::Write; | ^^^^^^^^^^^^^^ | = note: `#[warn(unused_imports)]` on by default warning: type alias `Map` is never used --> src/main.rs:4:6 | 4 | type Map<K, V> = BTreeMap<K, V>; | ^^^ | = note: `#[warn(dead_code)]` on by default warning: type alias `Set` is never used --> src/main.rs:5:6 | 5 | type Set<T> = BTreeSet<T>; | ^^^ warning: type alias `Deque` is never used --> src/main.rs:6:6 | 6 | type Deque<T> = VecDeque<T>; | ^^^^^
ソースコード
use std::collections::*;use std::io::Write;type Map<K, V> = BTreeMap<K, V>;type Set<T> = BTreeSet<T>;type Deque<T> = VecDeque<T>;fn run() {input! {n: usize,p: [(i64, i64); n],}let mut point = p;point.sort();if point.len() > 2 {let sign = |a: usize, b: usize, c: usize| -> i64 {let a = point[a];let b = point[b];let c = point[c];let ab = (b.0 - a.0, b.1 - a.1);let bc = (c.0 - b.0, c.1 - b.1);ab.0 * bc.1 - ab.1 * bc.0};let n = point.len();let mut hull = vec![0];let mut fix = 0;for i in (1..n).chain((0..(n - 1)).rev()) {while hull.len() > fix + 1 {let len = hull.len();if sign(hull[len - 2], hull[len - 1], i) >= 0 {hull.pop();} else {break;}}hull.push(i);if i == n - 1 {fix = hull.len() - 1;}}hull.pop();point = hull.into_iter().map(|k| point[k]).collect();}let mut p = point;let n = p.len();let mut ans = 0;for _ in 0..2 {argument_sort(&mut p);let mut pos = 0;for i in 0..n {let (x, y) = p[i];let mut f = |p: (i64, i64)| -> i64 {let s = x * p.1 - y * p.0;ans = ans.max(s.abs());s};if pos == i {pos = (pos + 1) % n;}while pos != i {let a = p[pos];let b = p[(pos + 1) % n];if f(a) <= f(b) {pos = (pos + 1) % n;} else {break;}}}p.iter_mut().for_each(|p| p.1 *= -1);}println!("{}", ans);}// https://judge.yosupo.jp/submission/27030 よりpub fn argument_sort(a: &mut [(i64, i64)]) {a.sort_by(|&(x1, y1), &(x2, y2)| {(y1 >= 0).cmp(&(y2 >= 0)).then_with(|| (x2 as i64 * y1 as i64).cmp(&(x1 as i64 * y2 as i64))).then_with(|| y1.cmp(&y2)) // (0, 0) < (x, y (> 0)).then_with(|| x2.cmp(&x1)) // (x1 (>= 0), 0) < (x2 (< 0), 0)});}fn main() {run();}// ---------- begin input macro ----------// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8#[macro_export]macro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();input_inner!{iter, $($r)*}};($($r:tt)*) => {let s = {use std::io::Read;let mut s = String::new();std::io::stdin().read_to_string(&mut s).unwrap();s};let mut iter = s.split_whitespace();input_inner!{iter, $($r)*}};}#[macro_export]macro_rules! input_inner {($iter:expr) => {};($iter:expr, ) => {};($iter:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($iter, $t);input_inner!{$iter $($r)*}};}#[macro_export]macro_rules! read_value {($iter:expr, ( $($t:tt),* )) => {( $(read_value!($iter, $t)),* )};($iter:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()};($iter:expr, chars) => {read_value!($iter, String).chars().collect::<Vec<char>>()};($iter:expr, bytes) => {read_value!($iter, String).bytes().collect::<Vec<u8>>()};($iter:expr, usize1) => {read_value!($iter, usize) - 1};($iter:expr, $t:ty) => {$iter.next().unwrap().parse::<$t>().expect("Parse error")};}// ---------- end input macro ----------