前往
大廳
主題

ZeroJudge - f438: 855 - Lunch in Grid City 解題心得

Not In My Back Yard | 2020-12-11 00:00:06 | 巴幣 0 | 人氣 265

題目連結:


題目大意:
輸入第一列給定一正整數 T ,代表有 T 筆測試資料。每筆測資第一列給定三正整數 S 、 A 、 F (S 、 A ≦ 1000 , 0 < F ≦ 50000),代表座標平面的最右上角之邊界為 (S, A),且現在有 F 個點。接著有 F 列,每列給定一個點之座標。

請從中找到一點,其與其他的點之曼哈頓距離(X 座標差的絕對值 + Y 座標差的絕對值)之總和是所有點中最小的。如果有多個這樣子的點,請輸出兩個座標值最小的那一組。



範例輸入:
2
2 2 2
1 1
2 2
7 7 11
1 2
1 7
2 2
2 3
2 5
3 4
4 2
4 5
4 6
5 3
6 5


範例輸出:
(Street: 1, Avenue: 1)
(Street: 3, Avenue: 4)


解題思維:
參見這題,而且這題不需要真的計算曼哈頓距離之和。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作