10000 Li chao by Fr0benius · Pull Request #16 · EbTech/rust-algorithms · GitHub
[go: up one dir, main page]

Skip to content

Li chao #16

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 10 commits into from
Mar 19, 2023
Merged
Changes from 1 commit
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
clippy
  • Loading branch information
Fr0benius committed May 22, 2022
commit c37757c498d0eb4dc067cb71f8ee30ea6972c5ff
8 changes: 4 additions & 4 deletions src/li_chao.rs
Original file line number Diff line number Diff line change
Expand Up @@ -38,16 +38,16 @@ impl LiChaoTree {
return;
}
let ix = ((r - self.left + l - self.left) / 2) as usize;
let x = self.left + (ix as i64);
let mid = self.left + (ix as i64);
let (ref mut m_ix, ref mut b_ix) = self.lines[ix];
if m * x + b > *m_ix * x + *b_ix {
if m * mid + b > *m_ix * mid + *b_ix {
std::mem::swap(&mut m, m_ix);
std::mem::swap(&mut b, b_ix);
}
if m < self.lines[ix].0 {
Copy link
Owner

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Why not use the m_ix variable again here?

self.add_line_impl(m, b, l, x);
self.add_line_impl(m, b, l, mid);
} else {
self.add_line_impl(m, b, x + 1, r);
self.add_line_impl(m, b, mid + 1, r);
}
}

Expand Down
0