回分類題庫
g055: D.阿里不達轟
關鍵字: NPSC 2009 國中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 37 Times / 34 Users | Submit : 71 Times / 38 Users | Accepted rate : 89%
題目加入時間 : 2011-12-26 15:00

Content: 简体中文

在阿里不達國的邊界,為了保護國土的安全,其實埋了很多遙控炸彈,每一顆炸彈都可以透過阿里不達國防部的控制遙控引爆。因為這些炸彈是分批製造的,所以每顆炸彈的爆炸半徑都有可能不一樣。

就在一個月黑風高的夜晚,守衛邊界的士兵發現炸彈區出現了許多圓形不明物體。因為擔心是鄰國的坦克偽裝,阿里不達國防部長決定把這些不明物體都炸掉。但因為遙控炸彈所費不貲,部長希望能用最少的炸彈解決所有的敵人。

Input:

第一行只有一個數字 T (T<=100),表示測資的數量。第二行開始為測資。
每筆測資的第一行有兩個數字 M, N (0<M<=15, 0<N<=9),分別表示炸彈的數量以及敵人的數量。
接下來的 M 行分別包含三個整數 X, Y, R,表示每個炸彈的X座標、Y座標以及半徑。接著 N 行同樣也包含三個整數 X, Y, R,表示每個敵方不明物體所在的X座標、Y座標以及半徑。
只要爆炸範圍有接觸到敵方物體的任何部分就算成功解決敵人。

Output:

對每一筆測資輸出最少必須使用的炸彈數量,若有炸不到的敵人則輸出Impossible,每筆測資一行。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
3 2
11 1 1
1 -1 1
5 0 5
10 0 1
0 0 1
2 2
11 1 1
1 -1 1
10 0 1
0 0 1
1 2
11 1 1
10 0 1
0 0 1

Sample Output :

1
2
Impossible

Hint :

Author :

NPSC 2009 國中組初賽 (管理員:sagit)

  Solve it!   Status Forum