孟加拉政府正在思考要如何解決達卡市的塞車問題，他們嘗試很多方向去解決這個問題。
上級長官 了解狀況的嚴重，他們向你求助於不同的看法與解決方法，作為一個資訊領域的你，給他們一個很簡單的想法，建造新的道路即可，但要確保這條新建道路可以使得旅途變短，這樣才能讓自動導航使用這條道路，進而改善塞車問題。
而達卡市的道路相當於無向圖，每個節點、邊分別對應站、道路。節點是由 2-D 平面的幾和點，而經由道路的花費由點與點的歐幾理德距離計算，現在只能新建一條道路，你將選擇其中兩個點建造出一條道路。
- 如果 (u, v) 本來就有一條道路，則不必考慮。
- 反之，Cuv = Sum (PreCostij -CurCostij)，CurCostij 表示加入新道路後的最短距離，而 PreCostij 表示之前的最短距離，將所有 i 到 j 都考慮，則最大的 Cuv 將會被選擇去新建。
Input
每組測資第一行有兩個整數 N, M (N <= 50, M <= 1225) ，
每組測資第一行有兩個整數 N, M (N <= 50, M <= 1225) ，
接下來會有 N 個點座標 (x, y), (-1000 <= x, y <= 1000)，而接下來會有 M 組 (u, v), (1 <= u, v <= N) 表示 u, v 之間已經有建造的道路。
Output
對於每組測資，輸出最大的 Cuv 對應的 (u, v)，其中 u 越小越好，相同時 v 越小越好。
對於每組測資，輸出最大的 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
Member of Elite Problemsetters' Panel
Special thanks to Tahseen Mohammad
沒有留言:
張貼留言