題目描述

在一個(gè)熱帶雨林中生存著一群猴子，它們以樹上的果子為生。昨天下了一場(chǎng)大雨，現(xiàn)在雨過天晴，但整個(gè)雨林的地表還是被大水淹沒著，部分植物的樹冠露在水面上。猴子不會(huì)游泳，但跳躍能力比較強(qiáng)，它們?nèi)匀豢梢栽诼冻鏊娴牟煌瑯涔谏蟻砘卮┧螅哉业较矚g吃的果實(shí)。

現(xiàn)在，在這個(gè)地區(qū)露出水面的有 N 棵樹，假設(shè)每棵樹本身的直徑都很小，可以忽略不計(jì)。我們?cè)谶@塊區(qū)域上建立直角坐標(biāo)系，則每一棵樹的位置由其所對(duì)應(yīng)的坐標(biāo)表示(任意兩棵樹的坐標(biāo)都不相同)。

在這個(gè)地區(qū)住著的猴子有 M 個(gè)，下雨時(shí)，它們都躲到了茂密高大的樹冠中，沒有被大水沖走。由于各個(gè)猴子的年齡不同、身體素質(zhì)不同，它們跳躍的能力不同。有的猴子跳躍的距離比較遠(yuǎn)(當(dāng)然也可以跳到較近的樹上)，而有些猴子跳躍的距離就比較近。這些猴子非常聰明，它們通過目測(cè)就可以準(zhǔn)確地判斷出自己能否跳到對(duì)面的樹上。

現(xiàn)已知猴子的數(shù)量及每一個(gè)猴子的最大跳躍距離，還知道露出水面的每一棵樹的坐標(biāo)，你的任務(wù)是統(tǒng)計(jì)有多少個(gè)猴子可以在這個(gè)地區(qū)露出水面的所有樹冠上覓食。

輸入描述

第 1 行為一個(gè)整數(shù)，表示猴子的個(gè)數(shù) (2≤M≤500)；

第 2 行為 M 個(gè)整數(shù)，依次表示猴子的最大跳躍距離（每個(gè)整數(shù)值在 1～1000之間）；

第 3 行為一個(gè)整數(shù)表示樹的總棵數(shù) (2≤N≤1000)；

第 4 行至第 N+3 行為 N 棵樹的坐標(biāo)（橫縱坐標(biāo)均為整數(shù)，范圍為：?1000～1000）。

（同一行的整數(shù)間用空格分開）

輸出描述

輸出一個(gè)整數(shù)，表示可以在這個(gè)地區(qū)的所有樹冠上覓食的猴子數(shù)。

輸入輸出樣例

示例 1

輸入

輸出

?

運(yùn)行限制

語(yǔ)言?最大運(yùn)行時(shí)間?最大運(yùn)行內(nèi)存

C++?1s?256M

C?1s?256M

Java?2s?256M

Python3?3s?256M

題目思路:

? ? ? ? 首先讀完題目就知道他要求的是最小生成樹,通過最小生成樹可以得到各個(gè)聯(lián)通點(diǎn)之間的距離，找到最大距離我們就可以和那些猴子的跳遠(yuǎn)距離比較，如果比他小則可以通過

? ? ? ? 我們還需要知道每?jī)蓚€(gè)點(diǎn)之間的距離，可以用公式sqrt((x1-x2)^2+(y1-y2)^2) 求出距離，把這些所求的距離放入一個(gè)類中保存，后期比較還需要用

? ? ? ? 最后我們生成最小生成樹來比較就可以了

看看代碼: