結果

問題 No.94 圏外です。(EASY)
ユーザー fmhr
提出日時 2016-07-25 12:21:56
言語 Go
(1.23.4)
結果
AC  
実行時間 30 ms / 5,000 ms
コード長 1,659 bytes
コンパイル時間 14,963 ms
コンパイル使用メモリ 225,768 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-26 07:59:55
合計ジャッジ時間 15,555 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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 // 重み
    count  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, count: count}
}
func (uf *UnionFind) Find(x int) int {
    if uf.par[x] == x {
        return x
    } else {
        uf.par[x] = uf.par[uf.par[x]]
        return uf.Find(uf.par[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)
}
func (uf UnionFind) test() {
    fmt.Println(uf.weight)
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0