結果

問題 No.94 圏外です。(EASY)
ユーザー Mao-betaMao-beta
提出日時 2024-03-06 16:50:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 350 ms / 5,000 ms
コード長 4,573 bytes
コンパイル時間 263 ms
コンパイル使用メモリ 81,828 KB
実行使用メモリ 204,240 KB
最終ジャッジ日時 2024-03-06 16:51:02
合計ジャッジ時間 8,150 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 284 ms
201,272 KB
testcase_01 AC 275 ms
201,016 KB
testcase_02 AC 275 ms
201,272 KB
testcase_03 AC 47 ms
57,828 KB
testcase_04 AC 278 ms
201,016 KB
testcase_05 AC 283 ms
200,760 KB
testcase_06 AC 287 ms
200,632 KB
testcase_07 AC 296 ms
200,248 KB
testcase_08 AC 312 ms
199,372 KB
testcase_09 AC 345 ms
204,112 KB
testcase_10 AC 332 ms
203,984 KB
testcase_11 AC 334 ms
203,856 KB
testcase_12 AC 332 ms
203,984 KB
testcase_13 AC 350 ms
203,856 KB
testcase_14 AC 332 ms
203,984 KB
testcase_15 AC 340 ms
204,240 KB
testcase_16 AC 338 ms
203,856 KB
testcase_17 AC 337 ms
203,984 KB
testcase_18 AC 333 ms
203,984 KB
testcase_19 AC 326 ms
203,856 KB
testcase_20 AC 283 ms
201,272 KB
testcase_21 AC 47 ms
57,828 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math
import bisect
from heapq import heapify, heappop, heappush
from collections import deque, defaultdict, Counter
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD99 = 998244353

input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()
SMI = lambda: input().split()
SLI = lambda: list(SMI())
EI = lambda m: [NLI() for _ in range(m)]

from collections import defaultdict


class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納　xが根のとき-(サイズ)を格納
        self.par = [-1 for i in range(n)]
        self.n = n
        self.roots = set(range(n))
        self.group_num = n


    def find(self, x):
        # 根ならその番号を返す
        if self.par[x] < 0:
            return x
        else:
            # 親の親は親
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def is_same(self, x, y):
        # 根が同じならTrue
        return self.find(x) == self.find(y)

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

        # 木のサイズを比較し、小さいほうから大きいほうへつなぐ
        if self.par[x] > self.par[y]:
            x, y = y, x

        self.group_num -= 1
        self.roots.discard(y)
        assert self.group_num == len(self.roots)

        self.par[x] += self.par[y]
        self.par[y] = x

    def size(self, x):
        return -self.par[self.find(x)]

    def get_roots(self):
        return self.roots

    def group_count(self):
        return len(self.roots)


def dist2(x1, y1, x2, y2):
    return (x1-x2)**2 + (y1-y2)**2


def ConvexHull(xy):
    def NG(x, y):
        x0, y0 = res[-2]
        x1, y1 = res[-1]
        return (x-x0)*(y1-y0)-(x1-x0)*(y-y0) >= 0

    res = []
    xy.sort()
    for x, y in xy:
        while len(res) > 1 and NG(x, y): res.pop()
        res.append((x, y))
    under_n = len(res)
    for x, y in xy[-2::-1]:
        while len(res) > under_n and NG(x, y): res.pop()
        res.append((x, y))
    return res[:-1]

def RotatingCalipers(xy):
    def dist(i, j):
        ix, iy = xy[i]
        jx, jy = xy[j]
        return (ix-jx)**2+(iy-jy)**2

    def vec(i):
        x0, y0 = xy[i]
        x1, y1 = xy[(i+1)%n]
        return x1-x0, y1-y0

    def outer(i, j):
        vix, viy = vec(i)
        vjx, vjy = vec(j)
        return vix*vjy-viy*vjx

    n = len(xy)
    if n < 2: return 0
    if n == 2: return dist(0, 1)**0.5
    res = 0
    i = xy.index(min(xy))
    j = xy.index(max(xy))
    si, sj = i, j
    while i != sj or j != si:
        res = max(res, dist(i, j))
        if outer(i, j) > 0: j = (j+1)%n
        else: i = (i+1)%n
    return res**0.5


def main():
    N = NI()
    XY = EI(N)
    XY = [[x+10000, y+10000] for x, y in XY]

    if N == 0:
        print(1)
        return
    if N == 1:
        print(2)
        return

    # B[x][y]: Xi//10 = x, Yi//10 = y となる点のリスト
    B = [[[] for _ in range(2001)] for _ in range(2001)]
    for i, (x, y) in enumerate(XY):
        B[x//10][y//10].append([x, y, i])

    # Bの8近傍+自身のみ通信可能か探索
    DX = [0, 1, 1, 1]
    DY = [1, 0, 1, -1]

    uf = UnionFind(N)

    for bx in range(2001):
        for by in range(2001):
            Bxy = B[bx][by]
            if len(Bxy) == 0:
                continue
            # 自身
            for x1, y1, i1 in Bxy:
                for x2, y2, i2 in Bxy:
                    if dist2(x1, y1, x2, y2) <= 100:
                        uf.unite(i1, i2)
            # 8近傍
            for dx, dy in zip(DX, DY):
                nbx = bx + dx
                nby = by + dy
                if 0 <= nbx < 2001 and 0 <= nby < 2001:
                    for x1, y1, i1 in Bxy:
                        for x2, y2, i2 in B[nbx][nby]:
                            if dist2(x1, y1, x2, y2) <= 100:
                                uf.unite(i1, i2)

    # 凸包
    groups = [uf.find(i) for i in range(N)]
    members = [[] for _ in range(N)]
    for i, g in enumerate(groups):
        members[g].append(i)

    ans = 0
    for r, M in enumerate(members):
        if len(M) <= 1:
            continue
        Vs = [XY[i] for i in M]
        Vs = ConvexHull(Vs)
        d = RotatingCalipers(Vs)
        ans = max(ans, d)

    print(ans+2)


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