結果

問題 No.96 圏外です。
ユーザー lam6er
提出日時 2025-03-31 17:39:30
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,122 bytes
コンパイル時間 265 ms
コンパイル使用メモリ 82,308 KB
実行使用メモリ 136,000 KB
最終ジャッジ日時 2025-03-31 17:40:39
合計ジャッジ時間 9,775 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math
from collections import defaultdict

def distance(p1, p2):
    return math.hypot(p1[0] - p2[0], p1[1] - p2[1])

def distance_sq(p1, p2):
    dx = p1[0] - p2[0]
    dy = p1[1] - p2[1]
    return dx * dx + dy * dy

def cross(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def convex_hull(points):
    sorted_points = sorted(points)
    lower = []
    for p in sorted_points:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    upper = []
    for p in reversed(sorted_points):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1]

def rotating_calipers(convex_points):
    n = len(convex_points)
    if n <= 1:
        return 0.0
    if n == 2:
        return distance(convex_points[0], convex_points[1])
    max_dist_sq = 0.0
    k = 1
    for i in range(n):
        j = (i + 1) % n
        while True:
            next_k = (k + 1) % n
            val_current = cross(convex_points[i], convex_points[j], convex_points[k])
            val_next = cross(convex_points[i], convex_points[j], convex_points[next_k])
            if val_next > val_current:
                k = next_k
            else:
                break
        dist_sq_ik = distance_sq(convex_points[i], convex_points[k])
        dist_sq_jk = distance_sq(convex_points[j], convex_points[k])
        current_max = max(dist_sq_ik, dist_sq_jk)
        if current_max > max_dist_sq:
            max_dist_sq = current_max
    return math.sqrt(max_dist_sq)

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 main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    n = int(input[idx])
    idx +=1
    points = []
    for _ in range(n):
        x = int(input[idx])
        y = int(input[idx+1])
        points.append((x, y))
        idx +=2

    if n == 0:
        print(1.0)
        return
    if n ==1:
        print(2.0)
        return

    cell_size = 10.0 / math.sqrt(2)
    uf = UnionFind(n)
    grid = defaultdict(list)

    for i in range(n):
        x, y = points[i]
        cx = math.floor(x / cell_size)
        cy = math.floor(y / cell_size)
        grid[(cx, cy)].append(i)

    for i in range(n):
        x, y = points[i]
        cx = math.floor(x / cell_size)
        cy = math.floor(y / cell_size)
        for dx in (-1, 0, 1):
            for dy in (-1, 0, 1):
                nc = (cx + dx, cy + dy)
                if nc not in grid:
                    continue
                for j in grid[nc]:
                    if j >= i:
                        continue
                    xi, yi = points[i]
                    xj, yj = points[j]
                    dx_ = xi - xj
                    dy_ = yi - yj
                    dist_sq = dx_*dx_ + dy_*dy_
                    if dist_sq <= 100.0 + 1e-9:
                        uf.union(i, j)

    components = defaultdict(list)
    for i in range(n):
        root = uf.find(i)
        components[root].append(points[i])

    max_diameter = 0.0
    for comp in components.values():
        if len(comp) ==0:
            continue
        ch = convex_hull(comp)
        if len(ch) ==0:
            diam = 0.0
        else:
            diam = rotating_calipers(ch)
        if diam > max_diameter:
            max_diameter = diam

    candidate = max_diameter + 2.0
    answer = max(candidate, 1.0)
    print("{0:.9f}".format(answer))

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