結果

問題 No.94 圏外です。(EASY)
ユーザー バカらっくバカらっく
提出日時 2019-09-28 14:29:39
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 2,034 bytes
コンパイル時間 87 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 11,904 KB
最終ジャッジ日時 2024-10-02 06:57:30
合計ジャッジ時間 2,839 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
11,392 KB
testcase_01 WA -
testcase_02 AC 33 ms
11,520 KB
testcase_03 AC 32 ms
11,392 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 464 ms
11,776 KB
testcase_20 AC 34 ms
11,392 KB
testcase_21 AC 34 ms
11,392 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# -*- 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)]):
        if (circle.x - circleList[k].x) * (circle.x - circleList[k].x) + (circle.y - circleList[k].y) * (
                circle.y - circleList[k].y) <= 200:
            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