題目連結: https://zerojudge.tw/ShowProblem?problemid=b582
# 解題思路
就是要找中位數 (就是最中間的那一個座標)，用 nth_element ()，可以順利找到那個數
但是，cin 的效率真的有一點點差...，所以用 scanf 替代吧！！(後來又發現 cout 的效率甚至比 printf 高？？)
# 程式碼
#include <bits/stdc++.h> | |
#define maxn 1000005 | |
#define ll long long | |
using namespace std; | |
ll px[maxn], py[maxn]; | |
int main(){ | |
srand(time(NULL)); | |
int t, n, x, y; | |
ll ans; | |
scanf("%d", &t); | |
while ( t-- ){ | |
scanf("%d", &n); | |
for ( int i=0; i<n; ++i ) | |
scanf("%lld%lld",&px[i],&py[i]); | |
nth_element(px, px+n/2, px+n); | |
x = px[n/2]; | |
nth_element(py, py+n/2, py+n); | |
y = py[n/2]; | |
ans = 0; | |
for ( int i=0; i<n; ++i ) | |
ans += abs(x-px[i])+abs(y-py[i]); | |
cout << ans << '\n'; | |
} | |
return 0; | |
} |
