QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#361612 | #8505. Almost Aligned | ucup-team635# | WA | 649ms | 86740kb | Rust | 3.7kb | 2024-03-23 12:01:16 | 2024-03-23 12:01:17 |
Judging History
answer
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 main() {
input! {
n: usize,
p: [(i64, i64, i64, i64); n],
}
let mut l = CHT::new(p.iter().map(|p| (-p.2, -p.0)).collect());
let mut r = CHT::new(p.iter().map(|p| (p.2, p.0)).collect());
let mut d = CHT::new(p.iter().map(|p| (-p.3, -p.1)).collect());
let mut u = CHT::new(p.iter().map(|p| (p.3, p.1)).collect());
let mut x = vec![0f64];
x.extend(l.enumerate());
x.extend(r.enumerate());
x.extend(d.enumerate());
x.extend(u.enumerate());
x.sort_by(|a, b| a.partial_cmp(b).unwrap());
x.retain(|x| *x >= 0f64);
let mut ans = std::f64::MAX;
for x in x {
ans = ans.min((r.find(x) + l.find(x)) * (u.find(x) + d.find(x)));
}
println!("{:.10}", ans);
}
// max cht
struct CHT {
po: usize,
line: Vec<(i64, i64)>, // (a, b) ax + b
}
impl CHT {
fn new(mut line: Vec<(i64, i64)>) -> Self {
line.sort();
line.dedup_by(|a, b| a.0 == b.0);
let mut stack = vec![line[0]];
for &(a, b) in line[1..].iter() {
while stack.len() >= 2 {
let len = stack.len();
let (c, d) = stack[len - 1];
let (e, f) = stack[len - 2];
//if (d - b) / (a - c) <= (
if (d - b) * (a - e) <= (f - b) * (a - c) {
stack.pop();
} else {
break;
}
}
stack.push((a, b));
}
Self { line: stack, po: 0 }
}
fn find(&mut self, x: f64) -> f64 {
let find = |k: usize| -> f64 {
let (a, b) = self.line[k];
a as f64 * x + b as f64
};
let mut po = self.po;
while po + 1 < self.line.len() && find(po) <= find(po + 1) {
po += 1;
}
let res = find(po);
self.po = po;
res
}
fn enumerate(&self) -> Vec<f64> {
self.line.windows(2).map(|line| {
let (a, b) = line[0];
let (c, d) = line[1];
(b - d) as f64 / (c - a) as f64
}).collect()
}
}
// ---------- 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 ----------
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 2076kb
input:
4 0 0 10 10 0 0 10 10 10 10 -10 -10 10 0 -20 0
output:
22.2222222222
result:
ok found '22.222222222', expected '22.222222222', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 2136kb
input:
3 0 -1 0 2 1 1 1 1 -1 1 -1 1
output:
0.0000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 2232kb
input:
3 0 -1 0 -2 1 1 1 1 -1 1 -1 1
output:
4.0000000000
result:
ok found '4.000000000', expected '4.000000000', error '0.000000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 2228kb
input:
1 0 0 0 0
output:
0.0000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 2112kb
input:
4 1000000 1000000 -1 -1000000 1000000 -1000000 -1000000 1 -1000000 -1000000 1 1000000 -1000000 1000000 1000000 -1
output:
3999984000032.0000000000
result:
ok found '3999984000032.000000000', expected '3999984000032.000000000', error '0.000000000'
Test #6:
score: -100
Wrong Answer
time: 649ms
memory: 86740kb
input:
1000000 -871226 486657 -467526 31395 -65837 846554 469710 -907814 927993 -45099 713462 -276539 261942 483255 746021 811070 63449 -779486 588838 -413687 812070 -87868 -813499 -420768 112521 -622607 -832012 921368 -182120 517379 -401743 -837524 -685985 337832 643014 135144 12895 326935 -495720 930620 ...
output:
3999984000012.0000000000
result:
wrong answer 1st numbers differ - expected: '3999996000000.0000000', found: '3999984000012.0000000', error = '0.0000030'