# Lấy nước (C or D mini, or B, C regular)

### Statement

Trên hệ trục tọa độ Oxy, cho đường thằng d: ax + by = 0 và n điểm có tọa độ lần lượt (x_1, y_1), (x_2, y_2), ..., (x_n, y_n). Nếu ta coi đường thẳng d là dòng sông (độ rộng của dòng sông xem như không đáng kể, rộng = 0) nhưng khi qua sông sẽ mất thời gian c, từng điểm là các hộ gia đình cần cấp nước. Bạn được cung cấp 1 xô nước. Bài toán đặt ra là:

Thật ra là có 2 bài có thể dựng lên:

1) bắt đầu từ hộ gia đình 1 ta cần lần lượt đi qua từng hộ gia đình theo thứ tự 1, 2, ..., n, ở mỗi hộ ta cần cấp nước cho hộ đó bằng việc đi từ hộ trước đó đến dòng sông, sau đó múc nước (thời gian múc nước là không đáng kể), rồi đi đến hộ tiếp theo để cấp nước. Yêu cầu tính thời gian di chuyển ít nhất, 1 đơn thời di chuyển sẽ ứng với 1 đơn vị độ dài. Nên tổng thời gian là = tổng các lần qua sông + thời gian đi
2) Bài toán thứ 2 là ta sẽ được chọn 1 lộ trình bất kì có thể đạt được thời gian ít nhất.

sol: toán c2, dp,
dùng toán để tính quãng đường, và dùng dp để tìm tối ưu

2 điểm nằm 2 bên đt thì cost = dist(A, B) + c
2 điểm nằm cùng bên đt thì lấy điểm của 1 trong 2 điểm qua đường thằng và tính khoản cách từ điểm còn lại tới điểm đối xứng, lấy B' là điểm đối xứng với B qua d thì cost = dist(A, B')