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