結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 35 ms
11,264 KB
testcase_01 WA -
testcase_02 AC 33 ms
11,264 KB
testcase_03 AC 32 ms
11,264 KB
testcase_04 WA -
testcase_05 AC 37 ms
11,520 KB
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 353 ms
11,904 KB
testcase_20 AC 32 ms
11,264 KB
testcase_21 WA -
権限があれば一括ダウンロードができます

ソースコード

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


def get_diff(circle1: tree_node, circle2: tree_node):
    diff_x = circle1.x - circle2.x
    diff_y = circle1.y - circle2.y
    return math.sqrt((diff_x * diff_x) + (diff_y * diff_y))


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 get_diff(circle, circleList[k]) <= 10.0:
            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)):
            if(j == k):
                continue
            diff = get_diff(currentList[j], currentList[k])
            diff += 2
            ans = max(ans, diff)

print(ans)
0