Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VODEFEND - Bảo vệ thành phố

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vodefend


Ở vương quốc Xa Rất Rất Xa, 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). Tuy thế giới vẫn đang trong thời gian hòa bình, vị vua của đất nước tin rằng họ phải luôn sẵn sàng bảo vệ đất nước. Quốc vương quyết định xây một tường thành khép kín có dạng một đa giác để bảo vệ một số thành phố của vương quốc. Các thành phố nằm trong và trên biên giới của tường thành này sẽ có thể yên tâm 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 thành kiên cố là vô cùng tốn kém, vì vậy, Quốc vương muốn chọn phương án xây tương thành có chu vi nhỏ nhất.

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 thành bao quanh ít nhất K thành phố với chu vi nhỏ nhất.

Input

  • Dòng thứ nhất gồm 2 số nguyên dương N, K.
  • N dòng tiếp theo: mỗi dòng chứa 2 số nguyên xi, yi là tọa độ của một thành phố trong vương quốc.

Output

  • Ghi ra một số nguyên duy nhất là độ dài nhỏ nhất của tường thành, với 4 chữ số sau dấu phẩy.

Giới hạn

  • 1 ≤ K ≤ N ≤ 50. Trong 35% số test có 1 ≤ K ≤ N ≤ 25.
  • Các tọa độ có giá trị tuyệt đối không vượt quá 106

Example

Input:
5 4
1 1
2 5
3 2
3 3
4 1

Output:
8.0645


Bài này có giá trị là 7 điểm.

Được gửi lên bởi:VOJ Team
Ngày:2012-12-12
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C C++ 4.3.2 CPP JAVA PAS-GPC PAS-FPC
Nguồn bài:VNOI Online 2013 - Ngày 2 - Lê Đôn Khuê

hide comments
2012-12-25 03:45:36 hiepsieunhan
cho em hoi bai e bi kq sai hay tle vay a !

Last edit: 2013-01-01 06:25:56
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.