結果
問題 | No.2173 Nightcord |
ユーザー | akakimidori |
提出日時 | 2022-12-25 00:38:06 |
言語 | Rust (1.77.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,564 bytes |
コンパイル時間 | 14,524 ms |
コンパイル使用メモリ | 380,200 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-04-29 06:35:18 |
合計ジャッジ時間 | 46,906 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 1,353 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 1 ms
5,376 KB |
testcase_09 | WA | - |
testcase_10 | AC | 506 ms
5,376 KB |
testcase_11 | WA | - |
testcase_12 | AC | 868 ms
5,376 KB |
testcase_13 | WA | - |
testcase_14 | AC | 1,167 ms
5,376 KB |
testcase_15 | AC | 1,135 ms
5,376 KB |
testcase_16 | AC | 3 ms
5,376 KB |
testcase_17 | AC | 153 ms
5,376 KB |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | AC | 572 ms
5,376 KB |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | AC | 847 ms
5,376 KB |
testcase_24 | AC | 1,697 ms
5,376 KB |
testcase_25 | AC | 1,130 ms
5,376 KB |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | AC | 193 ms
5,376 KB |
testcase_30 | AC | 1,851 ms
5,376 KB |
testcase_31 | WA | - |
testcase_32 | AC | 648 ms
5,376 KB |
testcase_33 | AC | 1,251 ms
5,376 KB |
testcase_34 | AC | 1,346 ms
5,376 KB |
testcase_35 | AC | 642 ms
5,376 KB |
testcase_36 | AC | 764 ms
5,376 KB |
testcase_37 | AC | 1,184 ms
5,376 KB |
testcase_38 | AC | 192 ms
5,376 KB |
testcase_39 | AC | 625 ms
5,376 KB |
testcase_40 | AC | 1,310 ms
5,376 KB |
testcase_41 | AC | 799 ms
5,376 KB |
testcase_42 | AC | 801 ms
5,376 KB |
testcase_43 | AC | 96 ms
5,376 KB |
testcase_44 | AC | 1 ms
5,376 KB |
testcase_45 | AC | 296 ms
5,376 KB |
testcase_46 | AC | 466 ms
5,376 KB |
testcase_47 | AC | 422 ms
5,376 KB |
testcase_48 | AC | 199 ms
5,376 KB |
testcase_49 | AC | 10 ms
5,376 KB |
testcase_50 | AC | 75 ms
5,376 KB |
testcase_51 | AC | 462 ms
5,376 KB |
testcase_52 | AC | 6 ms
5,376 KB |
testcase_53 | AC | 498 ms
5,376 KB |
testcase_54 | AC | 715 ms
5,376 KB |
testcase_55 | AC | 151 ms
5,376 KB |
testcase_56 | AC | 303 ms
5,376 KB |
ソースコード
fn main() { input! { n: usize, k: usize, p: [(i64, i64, usize1); n], } let ans = (|| -> bool { let mut a = vec![vec![]; 2]; for (x, y, c) in p { a[c].push((x, y)); } if a[0].is_empty() || a[1].is_empty() { return false; } for _ in 0..2 { for &orig in a[0].iter() { let mut point = a[1] .iter() .map(|p| { let x = p.0 - orig.0; let y = p.1 - orig.1; let g = gcd(x, y); (x / g, y / g) }) .collect::<Vec<_>>(); point.sort(); point.dedup(); if point .iter() .any(|p| point.binary_search(&(-p.0, -p.1)).is_ok()) { return true; } } a.swap(0, 1); } if k == 3 { return false; } let mut hull = vec![]; for i in 0..2 { let mut point = a[i].clone(); point.sort(); point.dedup(); 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 s = point[0]; point.push(s); for &(x, y) in a[i ^ 1].iter() { if point.windows(2).all(|a| { let (s, t) = (a[0], a[1]); (t.0 - s.0) * (y - s.1) - (t.1 - s.1) * (x - s.0) >= 0 }) { return true; } } hull.push(point); } for a in hull[0].windows(2) { for b in hull[1].windows(2) { let (p, q) = (a[0], a[1]); let (r, s) = (b[0], b[1]); let a = (q.0 - p.0) as i128; let b = (-(q.1 - p.1)) as i128; let e = (p.1 * q.0 - p.0 * q.1) as i128; let c = (s.0 - r.0) as i128; let d = (-(s.1 - r.1)) as i128; let f = (r.1 * s.0 - r.0 * s.1) as i128; let mut det = a * d - b * c; let mut x = e * d + f * -b; let mut y = e * -c + f * a; if det == 0 { continue; } if det < 0 { det = -det; x = -x; y = -y; } let p = (p.0 as i128, p.1 as i128); let q = (q.0 as i128, q.1 as i128); if det * p.0.min(q.0) <= x && x <= det * p.0.max(q.0) && det * p.1.min(q.1) <= y && y <= det * p.1.max(q.1) { return true; } } } false })(); let s = if ans {"Yes"} else {"No"}; println!("{}", s); } fn gcd(a: i64, b: i64) -> i64 { if b == 0 { a.abs() } else { gcd(b, a.abs() % b.abs()) } } // ---------- 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 ----------