a573.
ITSA2012 桂冠 元件計算
內容
| 元件計算 |
Background
由於在賽後無法得到題目描述與測資，小光盡可能地將原本題目描述清楚。
The Problem
在平面上給定 N 個相同半徑 R 的圓，如果兩個圓有相交，則它們屬於同一個元件(component)，而詢問有多少個不同的 component。
如圖所示 7 個圓，3 個 component。
輸入說明
測資第一行有一個整數 t，代表接下來有 t 組測試資料。
每組第一行有兩個正整數 N R，分別代表 N 個圓、半徑 R。
接下來有 N 行圓心座標 x, y。
數據範圍 N, x, y <= 60000，R <= 300
測試資料中，圓不會太密集。
輸出說明
對於每組測試資料輸出一行 component 個數。
範例輸入
#1
2 3 100 0 0 100 0 1000 1000 6 300 0 0 0 600 600 0 600 600 10000 0 0 10000
範例輸出
#1
2 3
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (99%): 3.0s , <10M
公開 測資點#1 (1%): 3.0s , <10M
公開 測資點#0 (99%): 3.0s , <10M
公開 測資點#1 (1%): 3.0s , <10M
提示 ：
標籤:
出處:
ITSA2012
[管理者：
morris1028
(碼畜)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||