# LineContainer

Authors: Benjamin Qi, Andi Qu

Convex Containers

## Half-Plane Intersection

Resources | |||
---|---|---|---|

CF | |||

Petr | Expected linear time! |

### This section is not complete.

*Example problem + implementation?*

Status | Source | Problem Name | Difficulty | Tags | Solution |
---|---|---|---|---|---|

Kattis | Normal | View Solution | |||

JOI | Hard | View Solution | |||

Balkan OI | Very Hard | ## Show TagsGeometry, Binary Search | External Sol |

## LineContainer (aka $O(N \log N)$ CHT)

Status | Source | Problem Name | Difficulty | Tags | Solution |
---|---|---|---|---|---|

YS | Normal | View Solution |

Resources | |||
---|---|---|---|

KACTL | source of code that I (Ben) use | ||

cp-algo | related topic (but not the same) |

### Example Problem

Focus Problem – read through this problem before continuing!

#### Analysis

Instead of focusing on the pillars that should be destroyed, let's instead focus on the pillars that remain.

The total cost consists of the cost due to height differences plus the cost of destroying unused pillars. The latter cost is equal to the cost to destroy all pillars minus the cost to destroy the remaining pillars.

Since the cost to destroy all pillars is constant, we can thus turn the problem into one about building pillars instead of destroying them!

From this, we get a basic DP recurrence. Let $dp[i]$ be the minimum cost to build the bridge so that the last build pillar is pillar $i$.

$dp[1] = -w_1$ and the following recurrence holds:

$\begin{aligned} dp[i] &= \min_{j < i}(dp[j] + (h_j - h_i)^2 - w_i)\\ &= \min_{j < i}(dp[j] + h_j^2 - 2h_ih_j) + h_i^2 - w_i \end{aligned}$Notice how

$dp[j] + h_j^2 - 2h_ih_j$effectively describes a linear function $y = mx + c$, where $m = -2h_j$, $x = h_i$, and $c = dp[j] + h_j^2$

This means that we can use CHT to compute $dp[i]$ efficiently!

However, since $m$ is not monotonic, we can't use linear CHT using a deque, so we must settle with $O(N \log N)$.

Code

## Problems

Status | Source | Problem Name | Difficulty | Tags | Solution |
---|---|---|---|---|---|

YS | Normal | View Solution | |||

POI | Normal | ## Show TagsDP, convex | View Solution | ||

CEOI | Hard | ## Show TagsDP, convex | External Sol | ||

FHC | Hard | ## Show TagsDP, convex | Check FHC | ||

AC | Hard | Check AC | |||

TLX | Hard | Check TLX | |||

Old Gold | Hard | External Sol |