結果

問題 No.2353 Guardian Dogs in Spring
ユーザー navel_tos
提出日時 2023-06-16 22:37:11
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,379 bytes
コンパイル時間 768 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 511,788 KB
最終ジャッジ日時 2024-06-24 15:19:22
合計ジャッジ時間 4,998 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3 TLE * 1 -- * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder393D

'''
「近い奴とつねに向き合う」ってしょうもな貪欲法するか。
ただN=8000だとちょっと制約がきついなぁ。

え、この貪欲落ちるの？

えーTLE。かなしい。

どうしよう。最小全域木でも作る？
'''
from fractions import Fraction as Fc
from collections import defaultdict as dd, deque as dq
import heapq as hq
f=lambda:tuple(map(int,input().split()))

#直線の切片のx座標y座標を返す
def line(P,Q):
    x1,y1=P; x2,y2=Q
    if x1==x2: return (x1,10**18)
    R=Fc(y2-y1,x2-x1); return (R,-R*x1+y1)

N=int(input()); N=N//2*2; P=[f() for _ in range(N)]; print(N//2)
Q=[]; G=[[] for _ in range(N)]; visited=[0]*N; visited[0]=1
for next in range(1,N):
    hq.heappush(Q,((P[0][0]-P[next][0])**2+(P[0][1]-P[next][1])**2,next,0))

#MST
while Q:
    dist,now,back=hq.heappop(Q)
    if visited[now]: continue
    G[now].append(back); G[back].append(now); visited[now]=1
    for next in range(N):
        if visited[next]: continue
        hq.heappush(Q,((P[now][0]-P[next][0])**2+(P[now][1]-P[next][1])**2,next,now))

#答えを探索
Q=dq(); looked=[0]*N
for now in range(N):
    if len(G[now])==1: Q.append(now)
while Q:
    now=Q.popleft()
    if looked[now]: continue
    looked[now]=1
    for next in G[now]:
        if looked[next]: continue
        print(now+1,next+1); looked[next]=1; break
0