Phủ sóng các thành phố trọng điểm

Binary-search Buổi 07 — Struct & File I/O Buổi 08 — Contest Chặng 1 sorting
Points
55
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Trên một tuyến đường cao tốc thẳng có $N$ thành phố. Thành phố thứ $i$ ở tọa độ $x_i$ và có độ trễ cho phép nghịch đảo bởi trọng số $w_i$. Nếu đặt một trạm phát sóng tại tọa độ $p$, chi phí trễ tại thành phố $i$ là $w_i \cdot |x_i - p|$. Bạn có tối đa $K$ trạm phát sóng được đặt tại bất kỳ tọa độ thực nào trên tuyến đường. Hãy tìm giá trị chi phí trễ lớn nhất nhỏ nhất có thể ($\min \max_{i} (w_i \cdot \min_j |x_i - p_j|)$). In kết quả làm tròn đến 4 chữ số thập phân.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N, K$. $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i$ và $w_i$.

Dữ liệu ra

Một số thực duy nhất làm tròn đến 4 chữ số thập phân.

Ví dụ
Input Output
3 1
0 1
10 1
5 2
5.0000
4 2
0 1
2 1
10 2
12 2
2.0000
Giới hạn
  • $1 \le K \le N \le 10^4$
  • $-10^6 \le x_i \le 10^6$, $1 \le w_i \le 1000$
Draft saved