Problem : 350 - D. 小紫愛打世紀帝國

Problem Statistics

Solved Member: 6　　Submission: 40　　User Tried: 8

Statement:

小紫是個有點害羞的平凡高中生，她有時會宅在家打世紀帝國。
世紀帝國是ㄧ個已經沒啥人在玩的即時戰略遊戲，既然是即時戰略遊戲，採收資源當然是一件很重要的事情！不論是綿羊，會撞死斥侯騎兵的野豬，還是路邊的金礦，都是非常重要的資源，有資源才可以蓋更多的建築物和生產更多的村民和軍隊，因此如何採資源也是這遊戲的重大課題。
由於小紫手速太低而且又有點手腦不協調，導致小紫的勝率只有7.1222%，這令小紫非常難過，因此小紫想要變強，她決定從「如何採資源」下手。
採資源的時候，需要把採到的資源放到一個收集站之後，才能開始利用這些資源。可想而知，如果收集站和資源離很遠的話，就要花很多無謂的時間走路，顯然十分的沒有效率，因此最佳的方法當然是直接把收集站蓋在她要的資源旁邊。但小紫認為蓋那麼多收集站實在是太辛苦了，因此為了簡化問題，她決定只蓋一個收集站，但這就又面臨了另外一個問題：那這個收集站應該要蓋在哪裡呢？
為了再一次的簡化問題，我們假設目前小紫所在的村莊為一個矩形，並且可以分割成若干塊地，且每塊地都有一個環境負載力，表示那塊地的資源豐富度。小紫想出了一個方法來判斷一塊地有多適合做為收集站。她認為環境負載力越高的地區應該要盡可能的離收集站近一些，這樣才可以更完善的利用資源。因此，除了收集站以外的地都會對該收集站產生一個「糟糕程度」，若某塊地的環境負載力為a，且那塊地與收集站的距離為d，那麼這塊地就會對該收集站ad^2的糟糕程度。因此小紫想要問你，究竟要把收集站設在哪裡，才能讓所有糟糕程度的和最小呢？

Input:Output:

第一行有一個t，表示再來有幾筆測試資料。
每筆測試資料中，第一行會有兩個整數n, m，表示小紫的基地的大小
接下來的n行，每行有m個數字，第i行第j個數字aij表示小紫的基地中每塊地的環境負載力。

對每筆測試資料，第一行請輸出一個整數p，表示最小的糟糕程度和。
下一行請輸出兩個整數x, y，表示收集站的最佳座標，最左上角的座標定義為(1, 1)，且最左下角的座標定義為(n, 1)、最右下角的座標定義為(n, m)，其餘請參照範例輸出。如果有多種可能，那麼就輸出x座標最小的那個，如果還是有多種可能，那麼就輸出y座標最小的。

Sample Input:Sample Output:

2
2 2
1 3
2 4
3 3
7 1 0
1 1 1
0 0 0

7
2 2
9
1 1

HINT:

40% 1 <= n, m <= 50、0 <= aij <= 1,000,000
100% 1 <= n, m <= 1,000、0 <= aij <= 1,000,000

Source:

2014 延平校內賽

Problem Setter

rilak

Testdata:

Test	Time	Memory	Score
0	1000ms	262144kb
1	1000ms	262144kb	20
2	1000ms	262144kb	20
3	3000ms	262144kb	20
4	3000ms	262144kb	20
5	3000ms	262144kb	20