Informatica Online Judge

  관개수로 [2336 / 0920]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 7   Total Tried : 9


The Champion of this Problem (C++) : gs18103 - ms / 1099byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]

Background

$N$개의 밭에 관개수로를 설치하고자 한다. $(1 <= N <= 2,000)$

각 밭 $i$는 2차원 평면으로 $(x_i, y_i)$ 로 표현되어 있고,

두 밭 $i$ 와 $j$ 사이에 수로를 만드는 비용은 다음과 같으며, 모든 밭이 최소 비용으로 모두 서로 연결되도록 하고 싶다.

$( 0 <= x_i, y_i <= 1000 )$

$(x_i - x_j)^2 + (y_i - y_j)^2$

문제는, 관개수로를 설치하는 업자는 비용이 적어도 $C( 1<=C <=1,000,000)$가 아니면 설치를 거부하려고 한다.

모든 밭을 관개수로로 연결할때 지불해야 할 최소 금액을 구하는 프로그램을 작성하시오.

Input

첫번째 줄에는 밭의 갯수$(N)$와 비용$(C)$이 입력된다.

두번째 줄부터는 밭의 위치$(X, Y)$값이 입력된다.

Output

밭을 연결하는 관개수로의 최소비용을 출력한다.

구축할 수 없는 경우에는 -1을 출력한다.

IO Example

<입력 예>
3 11
0 2
5 0
4 3

<출력 예>
46

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]