Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package main
- import (
- "fmt"
- "math"
- "math/rand"
- "sort"
- )
- var parents []int
- func dsu_get(vertex int) int{
- if vertex == parents[vertex]{
- return vertex
- }else{
- parents[vertex] = dsu_get(parents[vertex])
- return parents[vertex]
- }
- }
- func dsu_unite(a, b int){
- a = dsu_get(a)
- b = dsu_get(b)
- if rand.Int() & 1 == 1{tmp := a;a = b;b = tmp}
- if a != b{parents[a] = b}
- }
- type Point struct {
- x float64
- y float64
- }
- func (lhs Point) distanceTo(rhs Point) float64{return (lhs.x-rhs.x)*(lhs.x-rhs.x)+(lhs.y-rhs.y)*(lhs.y-rhs.y)}
- var points []Point
- type Edge struct {
- a_point_idx int
- b_point_idx int
- }
- func newEdge(a, b int)Edge{return Edge{a_point_idx: a,b_point_idx:b}}
- func (lhs Edge) less(rhs Edge) bool{return points[lhs.a_point_idx].distanceTo(points[lhs.b_point_idx]) < points[rhs.a_point_idx].distanceTo(points[rhs.b_point_idx])}
- func main() {
- n := 0
- fmt.Scan(&n)
- points = make([]Point, n)
- parents = make([]int,n)
- edges := make([]Edge, n*(n-1)/2)
- for i:=0; i < n; i++{
- x := 0; y:=0
- fmt.Scan(&x,&y)
- points[i] = Point{x:float64(x),y:float64(y)}
- parents[i] = i
- }
- idx := 0
- for i:= 0; i < n; i++{for j := i+1; j < n; j++{edges[idx] = newEdge(i,j);idx++}}
- sort.Slice(edges,func(i,j int)bool{return edges[i].less(edges[j])})
- var ans float64 = 0
- for i:=0; i<len(edges); i++{
- a := edges[i].a_point_idx; b := edges[i].b_point_idx
- if dsu_get(a)!= dsu_get(b){ans += math.Sqrt(points[edges[i].a_point_idx].distanceTo(points[edges[i].b_point_idx]));dsu_unite(a,b)}
- }
- ans = math.Round(ans*100)/100
- fmt.Printf("%0.2f\n",ans)
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement