Problem : 84 - 聖誕老人送禮物

Problem Statistics

Solved Member: 20　　Submission: 136　　User Tried: 22

Statement:

你還記得去年聖誕老人因為忘記送禮物給JOI村而被告到消基會嗎？

根據判決的結果，聖誕老人必須要還小孩們一個蛋糕。他必須趕快規劃送禮物的路線，而且，越快越好！

JOI村是這樣的，南北方向有 W 條道路，與東西方向的 H 條道路交叉而成，形成了棋盤狀的街道。南北向的道路由西往東編號為 1, 2, ... ,W ，並且東西向的道路也由南往北分別編號為 1, 2, ... ,H 。西邊算起第 x 條南北向道路與南邊開始算起的第 y 條東西樣道路的交叉口以座標 (x,y) 來表示。JOI村有 N 間房子需要送禮物，每間房子皆在十字路口的上面。

送禮物的過程當中，每移動到一個相鄰的十字路口所花的時間皆為 1 。他會在JOI村當中選一個十字路口作為他的降落地點，從那個地方開始分發禮物。並且，由於蛋糕的重量很重，他身上最多只能夠帶一個蛋糕行走，送完禮物後必須走回原地再拿下一個禮物到其他人家。直到送到最後一個人家裡，任務才算完成。

身為聖誕老人的好朋友，你不願意再看他送禮物送到TLE，你決定寫個程式幫他，計算在哪裡降落能夠使分發禮物的時間最短。

Task:

給你要送禮物的地點，請你計算聖誕老人要降落在哪裡才能夠使送禮時間最小。

Input:Output:

第1行有兩個數字，W, H，以空白區隔開來。
第2行有1個數字 N ，代表有多少戶人家需要送禮物。
接下來的 N 行每行有2個數字 Xi, Yi，以空白分隔開來，代表第 i 戶人家的座標。

第1行請你輸出1個整數，代表聖誕老人要完成送禮物最少需要的時間。
第2行請你輸出2個整數 X, Y，以空隔分開來，代表聖誕老人應該要降落的十字路口座標。
如果存在多個座標能使時間為最短，請輸出X最小的那一個，若還是有多組解答，請輸出最小的Y座標。

Sample Input:Sample Output:

SAMPLE A:
5 4
3
1 1
3 4
5 3

SAMPLE B:
4 6
8
1 3
3 2
4 4
2 5
2 3
3 3
3 4
2 4

SAMPLE A:
10
3 3

SAMPLE B:
21
2 3

HINT:

1 ≤ W ≤ 1000000000 = 10^9，代表南北向道路的數目
1 ≤ H ≤ 1000000000 = 10^9，代表東西向道路的數目
1 ≤ N ≤ 100000 = 10^5，需要送禮的房子數
1 ≤ Xi ≤ W，代表第 i 間房子所在南北方向道路的編號
1 ≤ Yi ≤ H，代表第 i 間房子所在東西方向道路的編號

40%測資滿足： N ≤ 1000
10%測資滿足： W ≤ 50, H ≤ 50, N ≤ 1000

SAMPLE A的移動範例
* 交叉點(3, 3) 降落
* 交叉點(3, 4) 送禮，共耗時1
* 交叉點(3, 3) 回到基地，共耗時2
* 交叉點(5, 3) 送禮，共耗時4
* 交叉點(3, 3) 回到基地，共耗時6
* 交叉點(1, 1) 送最後一次禮物，共耗時10

故最短耗時為10，降落地點為(3,3)。

Source:

JOI 2010/2011 本選

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	1500ms	65536kb
0-2	1500ms	65536kb
1-1	1500ms	65536kb	5
1-2	1500ms	65536kb
1-3	1500ms	65536kb
1-4	1500ms	65536kb
1-5	1500ms	65536kb
2-1	1500ms	65536kb	5
2-2	1500ms	65536kb
2-3	1500ms	65536kb
2-4	1500ms	65536kb
2-5	1500ms	65536kb
3-1	1500ms	65536kb	5
3-2	1500ms	65536kb
3-3	1500ms	65536kb
3-4	1500ms	65536kb
3-5	1500ms	65536kb
4-1	1500ms	65536kb	5
4-2	1500ms	65536kb
4-3	1500ms	65536kb
4-4	1500ms	65536kb
4-5	1500ms	65536kb
5-1	1500ms	65536kb	5
5-2	1500ms	65536kb
5-3	1500ms	65536kb
5-4	1500ms	65536kb
5-5	1500ms	65536kb
6-1	1500ms	65536kb	5
6-2	1500ms	65536kb
6-3	1500ms	65536kb
6-4	1500ms	65536kb
6-5	1500ms	65536kb
7-1	1500ms	65536kb	5
7-2	1500ms	65536kb
7-3	1500ms	65536kb
7-4	1500ms	65536kb
7-5	1500ms	65536kb
8-1	1500ms	65536kb	5
8-2	1500ms	65536kb
8-3	1500ms	65536kb
8-4	1500ms	65536kb
8-5	1500ms	65536kb
9-1	1500ms	65536kb	5
9-2	1500ms	65536kb
9-3	1500ms	65536kb
9-4	1500ms	65536kb
9-5	1500ms	65536kb
10-1	1500ms	65536kb	5
10-2	1500ms	65536kb
10-3	1500ms	65536kb
10-4	1500ms	65536kb
10-5	1500ms	65536kb
11-1	1500ms	65536kb	5
11-2	1500ms	65536kb
11-3	1500ms	65536kb
11-4	1500ms	65536kb
11-5	1500ms	65536kb
12-1	1500ms	65536kb	5
12-2	1500ms	65536kb
12-3	1500ms	65536kb
12-4	1500ms	65536kb
12-5	1500ms	65536kb
13-1	1500ms	65536kb	5
13-2	1500ms	65536kb
13-3	1500ms	65536kb
13-4	1500ms	65536kb
13-5	1500ms	65536kb
14-1	1500ms	65536kb	5
14-2	1500ms	65536kb
14-3	1500ms	65536kb
14-4	1500ms	65536kb
14-5	1500ms	65536kb
15-1	1500ms	65536kb	5
15-2	1500ms	65536kb
15-3	1500ms	65536kb
15-4	1500ms	65536kb
15-5	1500ms	65536kb
16-1	1500ms	65536kb	5
16-2	1500ms	65536kb
16-3	1500ms	65536kb
16-4	1500ms	65536kb
16-5	1500ms	65536kb
17-1	1500ms	65536kb	5
17-2	1500ms	65536kb
17-3	1500ms	65536kb
17-4	1500ms	65536kb
17-5	1500ms	65536kb
18-1	1500ms	65536kb	5
18-2	1500ms	65536kb
18-3	1500ms	65536kb
18-4	1500ms	65536kb
18-5	1500ms	65536kb
19-1	1500ms	65536kb	5
19-2	1500ms	65536kb
19-3	1500ms	65536kb
19-4	1500ms	65536kb
19-5	1500ms	65536kb
20-1	1500ms	65536kb	5
20-2	1500ms	65536kb
20-3	1500ms	65536kb
20-4	1500ms	65536kb
20-5	1500ms	65536kb