結果

問題 No.2909 Imaginary Summer
ユーザー ArcAkiArcAki
提出日時 2024-09-28 00:18:40
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,588 bytes
コンパイル時間 337 ms
コンパイル使用メモリ 82,448 KB
実行使用メモリ 124,468 KB
最終ジャッジ日時 2024-10-02 17:42:50
合計ジャッジ時間 8,958 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 1 TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

from sys import stdin
from heapq import heappop, heappush
INF = 1 << 60


class Node:
    def __init__(self, point, left=None, right=None, axis=0, mi1 = INF, mx1 = -INF, mi2 = INF, mx2 = INF):
        self.point = point
        self.left = left
        self.right = right
        self.axis = axis
        self.mi1 = mi1
        self.mx1 = mx1
        self.mi2 = mi2
        self.mx2 = mx2


class KDTree:
    def __init__(self):
        self.tree = []

    def build(self, points, d=0):
        if not points: return None
        mi1, mx1, mi2, mx2 = INF, -INF, INF, -INF
        for x, y in points:
            mi1 = min(mi1, x)
            mx1 = max(mx1, x)
            mi2 = min(mi2, y)
            mx2 = max(mx2, y)
        axis = 0 if (mx1-mi1) >= (mx2 - mi2) else 1
        points.sort(key=lambda p: p[axis])
        m = len(points) // 2
        mp = points[m]
        idx = len(self.tree)
        self.tree.append(Node(mp, None, None, axis, mi1, mx1, mi2, mx2))
        left = self.build(points[:m], d+1)
        self.tree[idx].left = left
        right = self.build(points[m+1:], d+1)
        self.tree[idx].right = right
        return idx

    def query(self, t, i, res):
        if i is None: return
        node = self.tree[i].point
        axis = self.tree[i].axis
        dist = dist_calc(node, t)
        if dist < res[1]:
            res[0] = node
            res[1] = dist
        nex, other = (self.tree[i].left, self.tree[i].right) if (axis==0 and t[0] < node[0]) or (axis==1 and t[1] < node[1]) else (self.tree[i].right, self.tree[i].left)
        if nex is not None:
            self.query(t, nex, res)
        if other is not None:
            mix, mxx, miy, mxy = self.tree[other].mi1, self.tree[other].mx1, self.tree[other].mi2, self.tree[other].mx2
            ad = possible_dist(node[0], node[1], mix, mxx, miy, mxy)
            if ad < res[1]:
                self.query(t, other, res)


def dist_calc(p, q):
    return (p[0]-q[0])**2+(p[1]-q[1])**2


def possible_dist(p, q, mi1, mx1, mi2, mx2):
    f1 = mi1 <= p <= mx1
    f2 = mi2 <= q <= mx2
    x = 0 if f1 else (mi1-p if p <= mi1 else p-mx1)
    y = 0 if f2 else (mi2-q if q <= mi2 else q-mx2)
    return x**2+y**2


def dijkstra(n, v, p, edge, s):
    time = [1e18]*n
    time[p] = 0
    used = [False]*n
    heap = [(0., p)]
    while heap:
        w, x = heappop(heap)
        if used[x]: continue
        used[x] = True
        time[x] = w
        for nex in edge[x]:
            if used[nex]:
                continue
            dx = (dist_calc(s[nex], s[x])**0.5)/v
            if time[nex] > w+dx:
                heappush(heap, (w+dx, nex))
    return time


def main():
    n, m, k = map(int, input().split())
    p = tuple(map(int, input().split()))
    s = [tuple(map(int, input().split()))for _ in range(n)]
    t = [tuple(map(int, input().split()))for _ in range(k)]
    v = float(input())
    edge = [[]for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    dic = dict()
    ans = 0.
    kdtree = KDTree()
    kdtree.build(s)
    hotel = [(0, 0), INF]
    kdtree.query(p, 0, hotel)
    for i in range(n):
        dic[s[i]] = i
    ss = dic[hotel[0]]
    pre = dist_calc(p, s[ss])**0.5
    time = dijkstra(n, v, ss, edge, s)
    for i in range(k):
        res = [(0, 0), INF]
        kdtree.query(t[i], 0, res)
        d1 = dist_calc(t[i], res[0])**0.5
        sub = time[dic[res[0]]]
        ans += min(dist_calc(p, t[i])**0.5, d1+sub+pre)*2.
    print(ans)


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