Giả sử có N thành phố được đánh số từ 1 đến N, thành phố thứ i nằm ở vị trí có tọa độ (xi, yi).
Trước diễn biến phức tạp của dịch COVID-19, chính phủ muốn xây dựng “vành đai an toàn” như một tường rào khép kín có dạng một đa giác để bảo vệ một số thành phố. Các thành phố nằm trong và trên biên giới của tường rào này sẽ yên tâm trong vận chuyển hàng hóa, đi lại và phát triển trong yên bình.
Để đảm bảo cho sự vững chắc của nền kinh tế, phải có ít nhất K thành phố được bảo vệ. Tuy nhiên, việc xây dựng một tường rào là vô cùng tốn kém, vì vậy chính phủ muốn chọn phương án xây tường rào có chu vi nhỏ nhất.
Yêu cầu: Cho tọa độ của N thành phố và số nguyên dương K, nhiệm vụ của bạn là tìm một tường rào bao quanh ít nhất K thành phố với chu vi nhỏ nhất. Giả sử có N thành phố được đánh số từ 1 đến N, thành phố thứ i nằm ở vị trí có tọa độ (xi, yi).
Trước diễn biến phức tạp của dịch COVID-19, chính phủ muốn xây dựng “vành đai an toàn” như một tường rào khép kín có dạng một đa giác để bảo vệ một số thành phố. Các thành phố nằm trong và trên biên giới của tường rào này sẽ yên tâm trong vận chuyển hàng hóa, đi lại và phát triển trong yên bình.
Để đảm bảo cho sự vững chắc của nền kinh tế, phải có ít nhất K thành phố được bảo vệ. Tuy nhiên, việc xây dựng một tường rào là vô cùng tốn kém, vì vậy chính phủ muốn chọn phương án xây tường rào có chu vi nhỏ nhất.
Yêu cầu: Cho tọa độ của N thành phố và số nguyên dương K, nhiệm vụ của bạn là tìm một tường rào bao quanh ít nhất K thành phố với chu vi nhỏ nhất.
