結果

問題 No.96 圏外です。
ユーザー lam6er
提出日時 2025-03-20 20:31:17
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,142 bytes
コンパイル時間 173 ms
コンパイル使用メモリ 82,508 KB
実行使用メモリ 133,952 KB
最終ジャッジ日時 2025-03-20 20:32:27
合計ジャッジ時間 10,343 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math
from collections import defaultdict

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return
        if self.rank[x_root] < self.rank[y_root]:
            self.parent[x_root] = y_root
        else:
            self.parent[y_root] = x_root
            if self.rank[x_root] == self.rank[y_root]:
                self.rank[x_root] += 1

def convex_hull(points):
    points = sorted(points)
    if len(points) <= 1:
        return points.copy()
    lower = []
    for p in points:
        while len(lower) >= 2:
            a = lower[-2]
            b = lower[-1]
            cross = (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0])
            if cross <= 0:
                lower.pop()
            else:
                break
        lower.append(p)
    upper = []
    for p in reversed(points):
        while len(upper) >= 2:
            a = upper[-2]
            b = upper[-1]
            cross = (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0])
            if cross <= 0:
                upper.pop()
            else:
                break
        upper.append(p)
    return lower[:-1] + upper[:-1]

def max_distance_convex(convex):
    n = len(convex)
    if n == 0:
        return 0.0
    if n == 1:
        return 0.0
    if n == 2:
        dx = convex[0][0] - convex[1][0]
        dy = convex[0][1] - convex[1][1]
        return math.hypot(dx, dy)
    max_dist_sq = 0.0
    j = 1
    m = len(convex)
    for i in range(m):
        next_j = (j + 1) % m
        while True:
            dx = convex[i][0] - convex[j][0]
            dy = convex[i][1] - convex[j][1]
            current_dist_sq = dx * dx + dy * dy
            if current_dist_sq > max_dist_sq:
                max_dist_sq = current_dist_sq
            a_x = convex[j][0] - convex[i][0]
            a_y = convex[j][1] - convex[i][1]
            b_x = convex[next_j][0] - convex[i][0]
            b_y = convex[next_j][1] - convex[i][1]
            cross = a_x * b_y - a_y * b_x
            if cross <= 0:
                break
            j = next_j
            next_j = (j + 1) % m
    return math.sqrt(max_dist_sq)

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr +=1
    points = []
    for _ in range(n):
        x = int(input[ptr])
        y = int(input[ptr+1])
        points.append( (x, y) )
        ptr +=2
    
    if n ==0:
        print(1.0)
        return
    
    buckets = defaultdict(list)
    for i, (x, y) in enumerate(points):
        bx = x // 10
        by = y // 10
        buckets[ (bx, by) ].append(i)
    
    uf = UnionFind(n)
    for i in range(n):
        x, y = points[i]
        bx = x // 10
        by = y // 10
        for dx in (-1, 0, 1):
            for dy in (-1, 0, 1):
                key = (bx + dx, by + dy)
                if key in buckets:
                    for j in buckets[key]:
                        if j <= i:
                            continue
                        xi, yi = points[i]
                        xj, yj = points[j]
                        dx_p = xi - xj
                        dy_p = yi - yj
                        dist_sq = dx_p**2 + dy_p**2
                        if dist_sq <= 100:
                            uf.union(i, j)
    
    groups = defaultdict(list)
    for i in range(n):
        root = uf.find(i)
        groups[root].append(points[i])
    
    max_candidate = 0.0
    for group in groups.values():
        if len(group) < 1:
            continue
        ch = convex_hull(group)
        d = max_distance_convex(ch)
        candidate = d + 2
        if candidate > max_candidate:
            max_candidate = candidate
    
    final_answer = max(max_candidate, 1.0)
    print("{0:.9f}".format(final_answer))

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