結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー Akijin_007
提出日時 2022-07-30 17:05:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 898 ms / 1,000 ms
コード長 2,012 bytes
コンパイル時間 501 ms
実行使用メモリ 83,252 KB
スコア 6,076,643
最終ジャッジ日時 2022-07-30 17:05:45
合計ジャッジ時間 30,099 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

def printout():
    for i in range(M):
        print(c[i], d[i])
    V = len(t)
    print(V)
    for i in range(V):
        print(t[i], r[i])

def fileout():
    f = open(r"C:\Users\AwanoShota\OneDrive\ドキュメント\kojinyou\atcoder\yukicoder_marathon\out.txt", "w")
    for i in range(M):
        f.write("{} {}\n".format(c[i], d[i]))
    V = len(t)
    f.write(str(V) + "\n")
    for i in range(V):
        f.write("{} {}\n".format(t[i], r[i]))

def calc_dis(t1, t2, u, v):
    if t1 == 1:
        x1 = a[u]
        y1 = b[u]
    else:
        x1 = c[u]
        y1 = d[u]
    if t2 == 1:
        x2 = a[v]
        y2 = b[v]
    else:
        x2 = c[v]
        y2 = d[v]
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5

import random
import time

N, M = map(int, input().split())
a = [0] * N
b = [0] * N
for i in range(N):
    a[i], b[i] = map(int, input().split())

ut = time.time()

c = [0] * M
d = [0] * M

for i in range(M):
    c[i] = random.randint(0, 1000)
    d[i] = random.randint(0, 1000)

while time.time() - ut < 0.8:
    sc = [0] * M
    sd = [0] * M
    pos = [0] * M
    for i in range(N):
        e = 0
        f = float("INF")
        for j in range(M):
            ff = calc_dis(1, 2, i, j)
            if f > ff:
                f = ff
                e = j
        pos[e] += 1
        sc[e] += a[i]
        sd[e] += b[i]

    for i in range(M):
        if pos[i] == 0:
            continue
        c[i] = round(sc[i] / pos[i])
        d[i] = round(sd[i] / pos[i])

pos = [[] for i in range(M)]

for i in range(N):
    e = 0
    f = float("INF")
    for j in range(M):
        ff = calc_dis(1, 2, i, j)
        if f > ff:
            f = ff
            e = j
    pos[e].append(i)

t = [1]
r = [1]

# print(pos)

for i in range(M):
    if len(pos[i]) == 0:
        continue
    t.append(2)
    r.append(i+1)
    for x in pos[i]:
        t.append(1)
        r.append(x+1)
        t.append(2)
        r.append(i+1)
    t.append(2)
    r.append(i+1)

t.append(1)
r.append(1)

printout()
0