結果

問題 No.94 圏外です。(EASY)
コンテスト
ユーザー szkhts
提出日時 2026-05-24 08:43:10
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
AC  
実行時間 218 ms / 5,000 ms
コード長 2,250 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 596 ms
コンパイル使用メモリ 20,828 KB
実行使用メモリ 15,484 KB
最終ジャッジ日時 2026-05-24 08:43:22
合計ジャッジ時間 5,288 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
import math

class UnionFind:
    def __init__(self, n):
        self.par = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x])
        return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)


def main():
    input = sys.stdin.readline
    N = int(input())

    if N == 0:
        # 中継局なし → 直接通信のみ
        print(1)
        return

    points = []
    for _ in range(N):
        x, y = map(int, input().split())
        points.append((x, y))

    uf = UnionFind(N)

    # 中継局間の距離が 10km 以下なら同じ連結成分にする
    for i in range(N):
        x1, y1 = points[i]
        for j in range(i + 1, N):
            x2, y2 = points[j]
            dx = x1 - x2
            dy = y1 - y2
            dist2 = dx * dx + dy * dy
            if dist2 <= 100:  # 10^2
                uf.unite(i, j)

    # 連結成分ごとに頂点を集める
    comp = {}
    for i in range(N):
        r = uf.find(i)
        if r not in comp:
            comp[r] = []
        comp[r].append(i)

    ans = 2.0  # 中継局が1本以上あれば、最低でも 2km は可能

    # 各成分内で最大距離を調べる
    for root, nodes in comp.items():
        m = len(nodes)
        if m == 1:
            # 1本だけの成分では d = 0 → d + 2 = 2 なので、既に ans に反映済み
            continue
        max_d2 = 0
        for i in range(m):
            x1, y1 = points[nodes[i]]
            for j in range(i + 1, m):
                x2, y2 = points[nodes[j]]
                dx = x1 - x2
                dy = y1 - y2
                d2 = dx * dx + dy * dy
                if d2 > max_d2:
                    max_d2 = d2
        d = math.sqrt(max_d2)
        ans = max(ans, d + 2.0)

    print("{:.10f}".format(ans))


if __name__ == "__main__":
    main()
0