a787. CPE：Lunch in Grid City (UVa 855)

題目描述

格子城市中的街道與大道形成規則方格，每個人住在一條街道與一條大道的交叉口。沿同一條街道或大道走到相鄰交叉口的距離是 1。 一群朋友要選擇交叉口作為午餐集合地點，使所有人從家走到集合點的距離總和最小。若有多個最佳地點，選擇街道編號較小者；仍相同時選擇大道編號較小者。

輸入格式

第一行是測試資料數 T。每筆第一行為正整數 S A F，分別表示街道數、大道數與朋友數，S ≤ 1000、A ≤ 1000、0 < F ≤ 50000。 接著 F 行，每行兩個整數，依序為一位朋友居住的街道與大道編號。街道編號為 1 至 S，大道編號為 1 至 A。

輸出格式

每筆一行，以 (Street: s, Avenue: a) 的格式輸出最佳地點的街道及大道編號，包含括號、標點與指定空格。

題目來源：UVa 855 — Lunch in Grid City。 原題：https://onlinejudge.org/external/8/855.pdf