結果

問題 No.1265 Balloon Survival
ユーザー lam6er
提出日時 2025-04-15 23:20:34
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,655 bytes
コンパイル時間 148 ms
コンパイル使用メモリ 81,416 KB
実行使用メモリ 93,296 KB
最終ジャッジ日時 2025-04-15 23:22:03
合計ジャッジ時間 3,402 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 4 WA * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    if N == 1:
        print(0)
        return
    points = []
    for _ in range(N):
        x = int(input[idx])
        y = int(input[idx+1])
        points.append((x, y))
        idx += 2
    x0, y0 = points[0]
    others = points[1:]
    M = len(others)
    if M == 0:
        print(0)
        return
    
    outgoing = [[] for _ in range(M)]
    incoming = [[] for _ in range(M)]
    
    for j in range(M):
        xj, yj = others[j]
        dx = xj - x0
        dy = yj - y0
        d_j1_sq = dx * dx + dy * dy
        
        for k in range(M):
            if k == j:
                continue
            xk, yk = others[k]
            dxjk = xj - xk
            dyjk = yj - yk
            d_jk_sq = dxjk * dxjk + dyjk * dyjk
            if d_jk_sq < d_j1_sq:
                outgoing[j].append(k)
                incoming[k].append(j)
    
    current_out_degree = [len(out) for out in outgoing]
    queue = deque()
    processed = [False] * M
    
    for j in range(M):
        if current_out_degree[j] == 0:
            queue.append(j)
    
    count_removed = 0
    
    while queue:
        u = queue.popleft()
        if processed[u]:
            continue
        processed[u] = True
        count_removed += 1
        
        for j in incoming[u]:
            if not processed[j]:
                current_out_degree[j] -= 1
                if current_out_degree[j] == 0 and not processed[j]:
                    queue.append(j)
    
    print(count_removed)

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