2013年7月30日 星期二

10724 - Road Construction

孟加拉政府正在思考要如何解決達卡市的塞車問題,他們嘗試很多方向去解決這個問題。

上級長官 了解狀況的嚴重,他們向你求助於不同的看法與解決方法,作為一個資訊領域的你,給他們一個很簡單的想法,建造新的道路即可,但要確保這條新建道路可以使得旅途變短,這樣才能讓自動導航使用這條道路,進而改善塞車問題。


而達卡市的道路相當於無向圖,每個節點、邊分別對應站、道路。節點是由 2-D 平面的幾和點,而經由道路的花費由點與點的歐幾理德距離計算,現在只能新建一條道路,你將選擇其中兩個點建造出一條道路。
  • 如果 (u, v)  本來就有一條道路,則不必考慮。
  • 反之,Cuv = Sum (PreCostij -CurCostij)CurCostij 表示加入新道路後的最短距離,而 PreCostij 表示之前的最短距離,將所有 ij 都考慮,則最大的 Cuv 將會被選擇去新建。

Input
每組測資第一行有兩個整數 N, M (N <= 50, M <= 1225) ,

接下來會有 N 個點座標 (x, y), (-1000 <= x, y <= 1000),而接下來會有 M(u, v), (1 <= u, v <= N) 表示 u, v 之間已經有建造的道路。

N = M = 0 時,結束程式。

Output
對於每組測資,輸出最大的 Cuv  對應的 (u, v),其中 u 越小越好,相同時 v 越小越好。
Cuv <= 1.0 時,則輸出 “No road required”。

Sample Input
Output for Sample Input
4 6
0 0 0 2 2 0 2 2
1 2 1 3 1 4
2 3 2 4
3 4
4 4
0 0 0 2 2 0 2 2
1 2 2 3 3 4 4 1
4 3
0 0 0 2 2 0 2 2
1 2 2 3 3 4
0 0
No road required
1 3
1 3

Problem setter: Md. Kamruzzaman
Member of Elite Problemsetters' Panel
Special thanks to Tahseen Mohammad