2349 問題 O: 信息學(xué)奧賽一本通T1437-擴(kuò)散
時間限制: 1s
內(nèi)存限制: 128MB 提交: 71 解決: 29
題目描述
一個點(diǎn)每過一個單位時間就會向四個方向擴(kuò)散一個距離，如圖。兩個點(diǎn)a、b連通，記作e(a,b),當(dāng)且僅當(dāng)a、b的擴(kuò)散區(qū)域有公共部分。連通塊的定義是塊內(nèi)的任意兩個點(diǎn)u、v都必定存在路徑e(u,a0),e(a0,a1),…,e(ak,v)。給定平面上的n給點(diǎn)，問最早什么時刻它們形成一個連通塊。
輸入
第一行一個數(shù)n，以下n行，每行一個點(diǎn)坐標(biāo)。
輸出
一個數(shù)，表示最早的時刻所有點(diǎn)形成連通塊。
樣例輸入
2 0 0 5 5
樣例輸出
5
提示
【數(shù)據(jù)規(guī)?！?/span>
對于20%的數(shù)據(jù)，滿足1≤N≤5;1≤X[i],Y[i]≤50;
對于100%的數(shù)據(jù)，滿足1≤N≤50;1≤X[i],Y[i]≤109。
比賽公告
測試題測試題測試題測試題測試題測試題測試題測試題測試題測試題