EWTD

6

Sep 22nd, 2021 (edited)
315
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.88 KB | None | 0 0
  1.  
  2.  
  3. package main
  4.  
  5. import (
  6. "fmt"
  7. "github.com/skorobogatov/input"
  8. "math"
  9. "sort"
  10. )
  11.  
  12. func col_road(n int) int {
  13. return ((n - 1) * n / 2)
  14. }
  15.  
  16. func filling_points(n int, points []Point2D, x,y float64) {
  17. for i := 0; i < n; i++ {
  18. input.Scanf("%f %f", &x, &y)
  19. points[i] = Point2D{x, y}
  20. }
  21. }
  22.  
  23. type Point2D struct {
  24. X, Y float64
  25. }
  26.  
  27. type Edge struct {
  28. IndexA, IndexB int
  29. Weight float64
  30. }
  31.  
  32. func check_distance(n int, edges []Edge,points []Point2D) {
  33. k := 0
  34. for i := 0; i < n; i++ {
  35. for j := i + 1; j < n; j++ {
  36. edges[k] = Edge{i, j, calcDistance(points[i],points[j])}
  37. k++
  38. }
  39. }
  40. }
  41.  
  42. func GetDistanceALL(point Point2D,another Point2D) (float64,float64) {
  43. legA := math.Abs(point.X - another.X)
  44. legB := math.Abs(point.Y - another.Y)
  45. return float64(math.Pow(legA,2)), float64(math.Pow(legB,2))
  46. }
  47.  
  48. func calcDistance(point Point2D, another Point2D) float64{
  49. b, a := GetDistanceALL(point ,another)
  50. return math.Sqrt(a + b)
  51. }
  52.  
  53.  
  54. func main() {
  55. var road int
  56. var Kruskal func (edges []Edge, ids []int) float64
  57. input.Scanf("%d",&road)
  58. points := make([]Point2D, road)
  59. edges := make([]Edge,col_road(road))
  60. var ids []int
  61. ids = make([]int, road)
  62. var x, y float64
  63. filling_points(road, points, x, y)
  64. check_distance(road, edges, points)
  65. for i := range ids {ids[i] = i}
  66. Kruskal = func(edges []Edge, ids []int) float64 {
  67. summaryWeight := 0.0
  68. counter := 0
  69. for i := 0; counter < len(ids) - 1; i++ {
  70. indexA, indexB := edges[i].IndexA, edges[i].IndexB
  71. if ids[indexA] != ids[indexB] {counter++;summaryWeight += edges[i].Weight
  72. oldId, newId := ids[indexB], ids[indexA]
  73. for j := 0; j < len(ids); j++ {
  74. if ids[j] == oldId {ids[j] = newId}
  75. }
  76. }
  77. }
  78. return summaryWeight
  79.  
  80. }
  81. cmp := func(i, j int) bool {return edges[i].Weight < edges[j].Weight}
  82. sort.Slice(edges, cmp)
  83. fmt.Printf("%.2fn", Kruskal(edges, ids))
  84. }
  85.  
  86.  
Add Comment
Please, Sign In to add comment