結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー titan23
提出日時 2022-07-30 16:51:22
言語 Text
(cat 8.3)
結果
WA  
実行時間 -
コード長 1,634 bytes
コンパイル時間 33 ms
実行使用メモリ 6,956 KB
スコア 0
最終ジャッジ日時 2022-07-30 16:51:34
合計ジャッジ時間 10,333 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge11
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import time
import random
input = lambda: sys.stdin.readline().rstrip()

#  -----------------------  #

n, m = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
ab_set = set(ab)
ALP = 5
LIMIT = 0.85
START = time.time()

def calc_score(root):
  ans = 0
  E = []
  for i in range(1, n):
    u, v = root[i][1]-1, root[i-1][1]-1
    tmp = ALP * ALP * ((ab[u][0] - ab[v][0])**2 + (ab[u][1] - ab[v][1])**2)
    E.append((i, tmp))
    ans += tmp
  v = root[-1][1]
  ans += ALP * ALP * ((ab[0][0] - ab[v][0])**2 + (ab[0][1] - ab[v][1])**2)
  E.sort(lambda x: -x[1])
  stations = []
  for i,c in E[:8]:
    u, v = root[i][1]-1, root[i-1][1]-1
    stations.append(((ab[u][0] + ab[v][0])//2, (ab[u][1] + ab[v][1])//2))
  for i in range(8):
    root.insert(E[i][0]+i, (2, i+1, 0))
  return root, stations, ans

def make_stations():
  stations = []
  return stations

def make_root():
  A = [(1, i, ab[i-1]) for i in range(1, n+1)]
  C = A[1:]

  c = []
  d = random.randint(50, 600)
  for i in (range(1000//d+2)):
    for j in (range(1000//d+2)):
      tmp = []
      for k in C:
        if d*i <= k[2][0] <= d*(i+1) and d*j <= k[2][1] <= d*(j+1):
          tmp.append(k)
      for t in tmp:
        C.remove(t) 
      tmp.sort(key=lambda x: x[2])
      c.extend(tmp)
  return A[:1] + c

vestscore = float('inf')
st, ro = [], []
while time.time() - START < LIMIT:
  root = make_root()
  root, stations, score = calc_score(root)
  if score < vestscore:
    vestscore = score
    st = stations[:]
    ro = root[:]
for i in st:
  print(*i[:2])
print(len(ro)+1)
for i,j,_ in ro:
  print(i, j)
print(1, 1)
0