/* -*- coding: utf-8 -*- * * 2315.cc: No.2315 Flying Camera - yukicoder */ #include #include using namespace std; /* constant */ const int MAX_N = 300; const int INF = 1 << 30; /* typedef */ /* global variables */ int xs[MAX_N], ys[MAX_N]; /* subroutines */ int calc(int n, int as[], int a0) { int sum = 0; for (int i = 0; i < n; i++) sum += abs(as[i] - a0); return sum; } int bsearch(int n, int as[]) { sort(as, as + n); int a0 = as[0], a1 = as[n - 1]; while (a0 + 2 < a1) { int aa0 = (a0 * 2 + a1) / 3; int aa1 = (a0 + a1 * 2) / 3; int c0 = calc(n, as, aa0); int c1 = calc(n, as, aa1); if (c0 > c1) a0 = aa0; else a1 = aa1; } int minc = INF; for (int a = a0; a <= a1; a++) minc = min(minc, calc(n, as, a)); return minc; } /* main */ int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d%d", xs + i, ys + i); int xc = bsearch(n, xs), yc = bsearch(n, ys); printf("%d\n", xc + yc); return 0; }