레이팅 미적용설명
비가 오지 않아 농부 존은 N개의 밭(1 <= N <= 2000) 사이에 물을 보내는 관개 시스템을 만들려고 한다.
각 밭 i는 2차원 평면 위의 서로 다른 점 (xi, yi)로 표현되며, 0 <= xi, yi <= 1000이다. 두 밭 i와 j 사이에 수도관을 설치하는 비용은 두 점 사이 유클리드 거리의 제곱, 즉 (xi - xj)^2 + (yi - yj)^2와 같다.
FJ는 모든 밭이 서로 연결되도록 최소 비용의 수도관 시스템을 만들고 싶다. 안타깝게도 시공업자는 비용(유클리드 거리의 제곱)이 C(1 <= C <= 1,000,000) 이상이 아닌 수도관은 설치를 거부한다.
FJ가 모든 밭을 수도관 네트워크로 연결하는 데 지불해야 하는 최소 금액을 계산하는 것을 도와라.
제약
입력 형식
첫째 줄: 정수 N과 C가 주어진다.
둘째 줄부터 1+N째 줄까지: i+1째 줄에는 정수 xi와 yi가 주어진다.
출력 형식
밭들을 연결하는 수도관 네트워크의 최소 비용을 출력한다. 그러한 네트워크를 만들 수 없으면 -1을 출력한다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
irrigation.in · 출력을 쓸 파일 irrigation.out예제 1
입력
3 11
0 2
5 0
4 3출력
46설명
Output details: FJ builds a pipe between (0,2) and (5,0) at cost 29, and between (0,2) and (4,3) at cost 17, for total 46.
문제 정보
태그