內容
在工廠裡面有許多搬運機器人負責搬運物品，每個機器人因為充電一次所能持續的時間有限，所以活動範圍限定以充電器為圓心的圓內(活動半徑按照機型而定)。如果兩台機器人有共同的活動範圍(活動範圍有相交或者接觸)，則可以互相傳遞物品。
給定編號1~N的N台機器人之充電器位置以及活動半徑，請問要把物品從1號機器人傳遞至N號機器人至少需要使用到幾台機器人？而在使用最少機器人的前提下，又有多少種方法可以傳遞呢(只要有用到不同的機器人就視為不同方法)？
輸入說明
輸入的第一行有一個正整數N，代表機器人的數量，2<=N<=5000
接下來的N行每行有四個整數 id x y r ，代表編號id的機器人充電器位置為(x,y)，活動半徑為r。
1<=id<=N, |x|<=1000, |y|<=1000, 1<=r<=100
輸出說明
輸出共有兩行
第一行有一個整數X，代表至少需要使用到幾台機器人。
第二行有一個數C，代表在使用最少機器人的前提下，傳遞物品的方法數%10007
傳遞物品的方法數保證>0
範例輸入
#1
2 1 0 0 3 2 1 0 2
範例輸出
#1
2 1
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
提示 ：
動態規劃(Dynamic Programming)
標籤:
出處:
2012 TOI模擬賽試題第1題
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||