EWTD

6

Sep 21st, 2021
799
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package main
  2.  
  3. import (
  4.     "fmt"
  5.     "math"
  6.     "math/rand"
  7.     "sort"
  8. )
  9.  
  10. var parents []int
  11. func dsu_get(vertex int) int{
  12.     if vertex == parents[vertex]{
  13.         return vertex
  14.     }else{
  15.         parents[vertex] = dsu_get(parents[vertex])
  16.         return parents[vertex]
  17.     }
  18. }
  19. func dsu_unite(a, b int){
  20.     a = dsu_get(a)
  21.     b = dsu_get(b)
  22.     if rand.Int() & 1 == 1{tmp := a;a = b;b = tmp}
  23.     if a != b{parents[a] = b}
  24. }
  25.  
  26. type Point struct {
  27.     x float64
  28.     y float64
  29. }
  30. func (lhs Point) distanceTo(rhs Point) float64{return (lhs.x-rhs.x)*(lhs.x-rhs.x)+(lhs.y-rhs.y)*(lhs.y-rhs.y)}
  31. var points []Point
  32. type Edge struct {
  33.     a_point_idx int
  34.     b_point_idx int
  35. }
  36.  
  37. func newEdge(a, b int)Edge{return Edge{a_point_idx: a,b_point_idx:b}}
  38. 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])}
  39.  
  40. func main() {
  41.     n := 0
  42.     fmt.Scan(&n)
  43.     points = make([]Point, n)
  44.     parents = make([]int,n)
  45.     edges := make([]Edge, n*(n-1)/2)
  46.     for i:=0; i < n; i++{
  47.         x := 0; y:=0
  48.         fmt.Scan(&x,&y)
  49.         points[i] = Point{x:float64(x),y:float64(y)}
  50.         parents[i] = i
  51.     }
  52.     idx := 0
  53.     for i:= 0; i < n; i++{for j := i+1; j < n; j++{edges[idx] = newEdge(i,j);idx++}}
  54.     sort.Slice(edges,func(i,j int)bool{return edges[i].less(edges[j])})
  55.     var ans float64 = 0
  56.     for i:=0; i<len(edges); i++{
  57.         a := edges[i].a_point_idx; b := edges[i].b_point_idx
  58.         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)}
  59.     }
  60.     ans = math.Round(ans*100)/100
  61.     fmt.Printf("%0.2f\n",ans)
  62. }
RAW Paste Data