Watering the Fields
Time limit1sMemory limit128 MB
Connect all fields with pipes costing at least C while minimizing total squared distance, or report -1 when impossible.
- Level
Medium4 of 10
- Topics
- Minimum spanning tree, Union-find, Sorting
- Solved
- No attempts yet
Problem
Farmer John needs an irrigation system between his N fields (1 ≤ N ≤ 2000) during a drought.
Field i is a distinct point (xi, yi) with 0 ≤ xi, yi ≤ 1000. A pipe between fields i and j costs the squared Euclidean distance:
(xi - xj)^2 + (yi - yj)^2
Build a minimum-cost network of pipes so every field can reach every other field through pipes.
The contractor installs a pipe only if its cost is at least C (1 ≤ C ≤ 1,000,000). Output the minimum total cost, or -1 if no such network exists.
Input
- Line 1: integers N and C
- Lines 2 through N+1: integers xi and yi for each field
Output
- Line 1: the minimum cost to connect all fields, or -1 if impossible