結果

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

ソースコード

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


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