結果

問題 No.94 圏外です。(EASY)
コンテスト
ユーザー バカらっく
提出日時 2019-09-28 14:36:10
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 2,034 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 338 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 12,160 KB
最終ジャッジ日時 2024-10-02 07:19:11
合計ジャッジ時間 2,085 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 RE * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# -*- coding:utf-8 -*-
import math
import queue


class tree_node:
    def __init__(self, id, x, y):
        self.id = id
        self.x = x
        self.y = y
        self.parent = None
        self.items = []
        self.__root:tree_node = None

    def add(self, child):
        child.parent = self
        self.items.append(child)
        if self.root is None:
            child.__root = self
        else:
            child.__root = self.root()

    def root(self):
        if self.__root is None:
            return self
        else:
            if self.__root.root().id != self.__root.id:
                self.__root = self.__root.root()
            return self.__root


circleCount = int(input())

circleList = [tree_node(k, v[0], v[1]) for k, v in
              enumerate(sorted([[int(j) for j in input().rstrip().split(" ")] for i in range(circleCount)]))]

for i, circle in enumerate(circleList):
    if i == 0:
        continue
    for k in reversed([j for j in range(0, i + 1)]):
        if (circle.x - circleList[k].x) * (circle.x - circleList[k].x) + (circle.y - circleList[k].y) * (
                circle.y - circleList[k].y) <= 100:
            circleList[k].root().add(circle)
            break
        if abs(circle.x - circleList[k].x) > 10:
            break

def getListFromTree(rootTreeNode):
    q = queue.Queue()
    nodeList = []
    q.put(rootTreeNode)
    while not q.empty():
        node = q.get()
        nodeList.append(node)
        for i in node.items:
            q.put(i)
    return nodeList


flags = {}

ans = 1
for i in circleList:
    if i.root().id in flags.keys():
        continue

    flags[i.root().id] = True
    currentList = getListFromTree(i.root())
    for j in range(len(currentList)):
        for k in range(j, len(currentList)):
            diff = math.sqrt((currentList[j].x - currentList[k].x)*(currentList[j].x - currentList[k].x)+(currentList[j].y - currentList[k].y)*(currentList[j].y - currentList[k].y))
            diff += 2
            ans = max(ans, diff)

print(ans)
0