読者です 読者をやめる 読者になる 読者になる

yukicoder No.94 圏外です。(EASY) Union-Find

No.94 圏外です。(EASY) - yukicoder

問題

二人は無線機をもっている。 N個の中継局(Xi,Yi)があり、二人が自由に移動できるとき、 二人が通信できる直線距離(ユークリッド距離)の最大値を求めよ。

無線機<->無線機 1km

中継局<->中継局 10km

無線機<->中継局 1km

N(0<=N<=1000)

解法

通信できる最も遠い2つの中継局を使うとき、二人の距離は最大になる。 中継局Aと中継局Bが通信できるかどうかをUnion Findで判定する。

package main

import (
    "fmt"
    "math"
)

type xy struct {
    x int
    y int
}

func isLink(a, b, c, d int) bool {
    return 100 >= (c-a)*(c-a)+(d-b)*(d-b)
}

func distance(a, b, c, d int) float64 {
    x := math.Sqrt(float64((c-a)*(c-a) + (b-d)*(b-d)))
    return x
}

func main() {
    var N int
    fmt.Scan(&N)
    repeater := make([]xy, N)
    for i := 0; i < N; i++ {
        fmt.Scan(&repeater[i].x, &repeater[i].y)
    }
    uf := NewUnionFind(N)
    for i := 0; i < N; i++ {
        for j := i; j < N; j++ {
            if isLink(repeater[i].x, repeater[i].y, repeater[j].x, repeater[j].y) {
                uf.Unit(i, j)
            }
        }
    }
    ans := 1.0
    for i := 0; i < N; i++ {
        for j := 0; j < N; j++ {
            if uf.Same(i, j) {
                ans = max(ans, 2+distance(repeater[i].x, repeater[i].y, repeater[j].x, repeater[j].y))
            }
        }
    }
    fmt.Println(ans)
}

func max(a, b float64) float64 {
    if a > b {
        return a
    } else {
        return b
    }
}

type UnionFind struct {
    par    []int // 親
    weight []int // 重み
}

func NewUnionFind(count int) *UnionFind {
    par := make([]int, count)
    weight := make([]int, count)
    for i := 0; i < count; i++ {
        par[i] = i
        weight[i] = 1
    }
    return &UnionFind{par: par, weight: weight}
}

func (uf *UnionFind) Find(x int) int {
    for uf.par[x] != x {
        uf.par[x] = uf.par[uf.par[x]]
        x = uf.par[x]
    }
    return x
}

func (uf *UnionFind) Unit(x, y int) {
    x = uf.Find(x)
    y = uf.Find(y)
    if x == y {
        return
    }
    if uf.weight[x] > uf.weight[y] {
        x, y = y, x
    }
    uf.par[x] = y
    uf.weight[y] += uf.weight[x]
}

func (uf *UnionFind) Same(x, y int) bool {
    return uf.Find(x) == uf.Find(y)
}

重み付きUnion-Findは以下を参照

https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf