# BUS
## Tác giả: Hồ Trọng Minh, I2023

### 1. Đề
Cho $n$ chiếc xe buýt xuất phát ở cùng địa điểm A tại các thời điểm $a_i$, kết thúc ở cùng địa điểm B tại các thời điểm $b_i$ cách A $l$ km.
Có $m$ vị khách đứng ở các địa điểm trên đoạn đường cách điểm A $x_i$ km và từng người sẽ lên chiếc xe buýt đầu tiên đi qua chỗ họ (nếu nhiều xe đến cùng lúc thì lên xe có số hiệu nhỏ nhất).
Với mỗi vị khách, xác định số hiệu của xe buýt người đó sẽ lên.

### 2. Lời giải
#### Thuật toán ngây thơ
Dễ thấy ta có thể dễ dàng giải quyết bài toán trong thời gian $O(n \times m)$ bằng cách duyệt qua từng chiếc xe cho mỗi vị khách và xem xe nào là xe tới đầu tiên. Tuy nhiên, ta sẽ bị TLE khi cài thuật toán này.

#### Thuật toán cải tiến

Nhận xét rằng mỗi xe buýt có thể được xem như một phương trình tuyến tính (do vận tốc của xe trong suốt quãng đường là không đổi) và mỗi vị khách có thể xem như một điểm.

Như vậy, bài toán trở thành: Cho trước một tập các phương trình đường thẳng, với mỗi điểm $x_i$, hãy tìm phương trình đường thẳng $f$ đầu tiên sao cho $f(x_i)$ đạt giá trị nhỏ nhất.

Đây là một bài toán cơ bản của dạng bài cải tiến bằng bao lồi và có thể được giải bằng các thuật toán như **Line container** hay **Li Chao tree** trong độ phức tạp $O(mlogl)$ hoặc $O(mlogn)$

**[Tìm hiểu về Line container](https://jeffreyxiao.me/blog/convex-hull-trick)
[Tìm hiểu về Li Chao tree](https://robert1003.github.io/2020/02/06/li-chao-segment-tree.html)**

**[Code Line container: O(mlogn) - Cre: Author](https://ideone.com/TrfDgE)
[Code Li Chao: O(mlogl) - Cre: Megumin](https://ideone.com/rC5hK6)**