結果
問題 | No.1144 Triangles |
ユーザー | akakimidori |
提出日時 | 2020-08-01 11:07:59 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 114 ms / 3,000 ms |
コード長 | 6,894 bytes |
コンパイル時間 | 12,711 ms |
コンパイル使用メモリ | 376,496 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-07 20:01:58 |
合計ジャッジ時間 | 13,046 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 25 |
ソースコード
// ---------- begin ModInt ----------mod modint {#[allow(dead_code)]pub struct Mod;impl ConstantModulo for Mod {const MOD: u32 = 1_000_000_007;}#[allow(dead_code)]pub struct StaticMod;static mut STATIC_MOD: u32 = 0;impl Modulo for StaticMod {fn modulo() -> u32 {unsafe { STATIC_MOD }}}#[allow(dead_code)]impl StaticMod {pub fn set_modulo(p: u32) {unsafe {STATIC_MOD = p;}}}use std::marker::*;use std::ops::*;pub trait Modulo {fn modulo() -> u32;}pub trait ConstantModulo {const MOD: u32;}impl<T> Modulo for TwhereT: ConstantModulo,{fn modulo() -> u32 {T::MOD}}pub struct ModInt<T>(pub u32, PhantomData<T>);impl<T> Clone for ModInt<T> {fn clone(&self) -> Self {ModInt::new_unchecked(self.0)}}impl<T> Copy for ModInt<T> {}impl<T: Modulo> Add for ModInt<T> {type Output = ModInt<T>;fn add(self, rhs: Self) -> Self::Output {let mut d = self.0 + rhs.0;if d >= T::modulo() {d -= T::modulo();}ModInt::new_unchecked(d)}}impl<T: Modulo> AddAssign for ModInt<T> {fn add_assign(&mut self, rhs: Self) {*self = *self + rhs;}}impl<T: Modulo> Sub for ModInt<T> {type Output = ModInt<T>;fn sub(self, rhs: Self) -> Self::Output {let mut d = T::modulo() + self.0 - rhs.0;if d >= T::modulo() {d -= T::modulo();}ModInt::new_unchecked(d)}}impl<T: Modulo> SubAssign for ModInt<T> {fn sub_assign(&mut self, rhs: Self) {*self = *self - rhs;}}impl<T: Modulo> Mul for ModInt<T> {type Output = ModInt<T>;fn mul(self, rhs: Self) -> Self::Output {let v = self.0 as u64 * rhs.0 as u64 % T::modulo() as u64;ModInt::new_unchecked(v as u32)}}impl<T: Modulo> MulAssign for ModInt<T> {fn mul_assign(&mut self, rhs: Self) {*self = *self * rhs;}}impl<T: Modulo> Neg for ModInt<T> {type Output = ModInt<T>;fn neg(self) -> Self::Output {if self.0 == 0 {Self::zero()} else {Self::new_unchecked(T::modulo() - self.0)}}}impl<T> std::fmt::Display for ModInt<T> {fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {write!(f, "{}", self.0)}}impl<T: Modulo> std::str::FromStr for ModInt<T> {type Err = std::num::ParseIntError;fn from_str(s: &str) -> Result<Self, Self::Err> {let val = s.parse::<u32>()?;Ok(ModInt::new(val))}}impl<T: Modulo> From<usize> for ModInt<T> {fn from(val: usize) -> ModInt<T> {ModInt::new_unchecked((val % T::modulo() as usize) as u32)}}impl<T: Modulo> From<i64> for ModInt<T> {fn from(val: i64) -> ModInt<T> {let m = T::modulo() as i64;ModInt::new((val % m + m) as u32)}}#[allow(dead_code)]impl<T> ModInt<T> {pub fn new_unchecked(d: u32) -> Self {ModInt(d, PhantomData)}pub fn zero() -> Self {ModInt::new_unchecked(0)}pub fn one() -> Self {ModInt::new_unchecked(1)}pub fn is_zero(&self) -> bool {self.0 == 0}}#[allow(dead_code)]impl<T: Modulo> ModInt<T> {pub fn new(d: u32) -> Self {ModInt::new_unchecked(d % T::modulo())}pub fn pow(&self, mut n: u64) -> Self {let mut t = Self::one();let mut s = *self;while n > 0 {if n & 1 == 1 {t *= s;}s *= s;n >>= 1;}t}pub fn inv(&self) -> Self {assert!(self.0 != 0);self.pow(T::modulo() as u64 - 2)}}#[allow(dead_code)]pub fn mod_pow(r: u64, mut n: u64, m: u64) -> u64 {let mut t = 1 % m;let mut s = r % m;while n > 0 {if n & 1 == 1 {t = t * s % m;}s = s * s % m;n >>= 1;}t}}// ---------- end ModInt ----------//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 より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_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_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")};}//use modint::*;type M = ModInt<Mod>;fn run() {input! {n: usize,p: [(i64, i64); n],}let mut p = p;p.sort_by_key(|p| (p.1, p.0));let mut ans = M::zero();for (i, &s) in p.iter().enumerate().take(n - 2) {let mut p: Vec<(i64, i64)> = p.iter().skip(i + 1).map(|p| (p.0 - s.0, p.1 - s.1)).filter(|p| *p != (0, 0)).collect();p.sort_by(|a, b| {(a.0 * b.1 - a.1 * b.0).cmp(&0)});p.reverse();assert!(p.windows(2).all(|p| p[0].0 * p[1].1 - p[0].1 * p[1].0 >= 0));let mut a = 0i64;let mut b = 0i64;for p in p.iter() {let s = a * p.1 - b * p.0;ans += ModInt::from(s);a += p.0;b += p.1;}}println!("{}", ans);}fn main() {run();}