回分類題庫
d051: 5.導彈攔截
關鍵字: 100年彰雲嘉區複賽

測資點 : 2 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 73 Times / 60 Users | Submit : 234 Times / 79 Users | Accepted rate : 76%
題目加入時間 : 2012-07-06 14:48

Content: 简体中文

某國研發出了一種新的導彈攔截系統,凡是與它的距離不超過其工作半徑的導彈都能夠被它成功攔截。當系統的工作半徑為0時,則能夠攔截與它位置恰好相同的導彈。但該導彈攔截系統存在這樣的缺陷:每套系統每天只能設定一次工作半徑。而當天的使用代價,就是所有系統工作半徑的平方和,例如某日系統 A 的工作半徑設定為 Ra、系統 B 的工作半徑設定為 Rb、而系統 C 的工作半徑設定為 Rc,則此三套系統當日的使用代價為 Ra2 + Rb2 + Rc2
某天,雷達捕捉到敵國的導彈來襲。由於該系統尚處於試驗階段,所以只有兩套系統在執勤當中。如果現在的要求是攔截所有的導彈,必須設定這兩套導彈攔截系統適當的半徑,請計算這一天的最小使用代價。

Input:

測試資料第一列有一正整數N表示測試資料組數
接下來有 N 組資料,每一組資料內容如下
第一列包含4 個整數 x1、y1、x2、y2,每兩個整數之間用一個空格隔開,表示這兩套導彈攔截系統的座標分別為 (x1, y1)、(x2, y2)。
第二列包含1個整數 M,表示有 M 顆導彈。接下來 M 列,每列兩個整數 x、y,中間用一個空格隔開,表示一顆導彈的座標 (x, y)。不同導彈的座標可能相同。

註:測試資料中的 M 值最大為 9。

Output:

每一組測試資料的輸出只有一列,包含一個整數,即當天的最小使用代價。若測試檔內有N組資料,則輸出N列。

Sample Input:help

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

Sample Output :

18
30

Hint :

Author :

100年彰雲嘉區複賽 (管理員:sagit)

  Solve it!   Status Forum