| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.1 초 | 16 MB | 2 | 0 | 0 | 0.000% |
Vlad really enjoys drawing points on a piece of paper. He has been doing it all day long, but now he decides that he wants to join some of these points using straight lines. There are N such points, numbered from 0 to N-1, and all of them have integer coordinates. Vlad wants to draw exactly K distinct line segments and for each line segment he chooses both endpoints from the set of points that he has already drawn. But that is not all - he also wants to minimize the total length of the line segments, which is the sum of all the lengths of the K line segments.
You are going to help Vlad to determine the total minimum length as well as all the mandatory points. A point is mandatory if and only if it will be used as an endpoint of a line segment to at least one of the K line segments, no matter how we choose them with respect to the minimal length condition. So, if we would erase a mandatory point we wouldn’t be able to obtain the same minimum length.
The input will have on the first line two positive integers: N and K. The following N lines will contain the coordinates of each point. All coordinates are integers. Keep in mind that the points are numbered from 0 to N-1!
On the first line of the output you should print the total minimum length, with an error of at most 10−4 (the first 4 decimals should be correct). The next lines will contain the indices of the mandatory points, sorted in ascending order. For details please refer to the example below.
6 3 1 2 4 5 2 3 1 1 8 8 7 4
4.65028 0 2 3