Hdu4311 || 4312Meeting point-1/-2 n个点中任意选一个点使得其余点到该点曼哈顿距离之和最小

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3448 Accepted Submission(s): 1144

Problem Description

It has been ten years since TJU-ACM established. And in this year all the retired TJU-ACMers want to get together to celebrate the tenth anniversary. Because the retired TJU-ACMers may live in different places around the world, it may be hard to find out where to celebrate this meeting in order to minimize the sum travel time of all the retired TJU-ACMers.
There is an infinite integer grid at which N retired TJU-ACMers have their houses on. They decide to unite at a common meeting place, which is someone's house. From any given cell, only 4 adjacent cells are reachable in 1 unit of time.
Eg: (x,y) can be reached from (x-1,y), (x+1,y), (x, y-1), (x, y+1).
Finding a common meeting place which minimizes the sum of the travel time of all the retired TJU-ACMers.

Input

The first line is an integer T represents there are T test cases. (0<T <=10)
For each test case, the first line is an integer n represents there are n retired TJU-ACMers. (0<n<=100000), the following n lines each contains two integers x, y coordinate of the i-th TJU-ACMer. (-10^9 <= x,y <= 10^9)

Output

For each test case, output the minimal sum of travel times.

Sample Input

-4 -1

-1 -2

2 -4

0 2

0 3

5 -2

0 0

2 0

-5 -2

2 -2

-1 2

4 0

-5 1

-1 3

3 1

3 -1

1 -1

-1 -1

-3 2

-4 4

5 2

5 -4

3 -1

4 3

-1 -2

3 4

-2 2

Sample Output

Hint

In the first case, the meeting point is (-1,-2); the second is (0,0), the third is (3,1) and the last is (-2,2)

Author

TJU

Source

2012 Multi-University Training Contest 2

题意：比较经典的题，给出n个点的坐标，从中选一个点，使得其余的n-1个点到该点的曼哈顿距离之和最小

曼哈顿距离：对于(x1,y1)和(x2,y2)，这两点的曼哈顿距离为abs(x1 - x2) + abs(y1 - y2)

思路：给出一维坐标上的n个数，要求从中找出一点，使得该点到其余点距离之和最小。大白里面有证明这n个数的中为数对应的点就是答案，但是我们仍然可以通过递推解决这个一维的问题，设sl[i]表示i的左边i-1个数到第i个数的距离之和，那么有sl[i] = sl[i-1] + (i-1) * (a[i] - a[i-1]); 同理sr[i]表示i的右边i-1个数到i的距离和，有sr[i] = sr[i+1] + (n-i) * (a[i+1]-a[i]); 这两个递推式成立的前提是序列有序。那么上面一维问题的答案就是min(sl[i] + sr[i]);

原题是2维的，但是我们可以分别考虑x,y，即对于每一个点，求出选该点时其余点到该点x方向的距离和以及y方向的距离和，那么min(ansx+ansy)就是答案

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
struct Point {
    int x, y, id;
    Point() {}
    Point(int x, int y, int id) : x(x), y(y), id(id) {}
};
Point p[N];
int n;
ll sl[N], sr[N], ansx[N], ansy[N];
int cmp1(Point a, Point b) { return a.x < b.x; }
int cmp2(Point a, Point b) { return a.y < b.y; }
void initx() {
    sort(p, p + n, cmp1);
    sl[0] = 0; sr[n - 1] = 0;
    for(int i = 1; i < n; ++i) sl[i] = sl[i - 1] + 1ll * i * (p[i].x - p[i - 1].x);
    for(int i = n - 2; i >= 0; --i) sr[i] = sr[i + 1] + 1ll * (n - i - 1) * (p[i + 1].x - p[i].x);
    for(int i = 0; i < n; ++i) ansx[ p[i].id ] = sl[i] + sr[i];
}
void inity() {
    sort(p, p + n, cmp2);
    sl[0] = 0; sr[n - 1] = 0;
    for(int i = 1; i < n; ++i) sl[i] = sl[i - 1] + 1ll * i * (p[i].y - p[i - 1].y);
    for(int i = n - 2; i >= 0; --i) sr[i] = sr[i + 1] + 1ll * (n - i - 1) * (p[i + 1].y - p[i].y);
    for(int i = 0; i < n; ++i) ansy[ p[i].id ] = sl[i] + sr[i];
}
int main() {
   // freopen("in.txt", "r", stdin);
    int _; scanf("%d", &_);
    while(_ --) {
        scanf("%d", &n);
        for(int i = 0; i < n; ++i) {
            scanf("%d%d", &p[i].x, &p[i].y);
            p[i].id = i;
        }
        initx();
        inity();
        ll ans = (1ll << 62);
        for(int i = 0; i < n; ++i) ans = min(ansx[i] + ansy[i], ans);
        printf("%I64d
", ans);
    }
    return 0;
}

View Code

hdu4312: 给出n个点的坐标，从中选一个点，使得其余的n-1个点到该点的切比雪夫距离之和最小

切比雪夫距离：对于(x1,y1)和(x2,y2)，这两点的曼哈顿距离为max（abs(x1 - x2) ， abs(y1 - y2)）

公式转化：max（abs(x1 - x2) ， abs(y1 - y2)） = abs((x1+y1)-(x2+y2)) + abs((x1-y1)-(x2-y2)); 那么另x = x1 + y1; y = x1 - y2; 就和4311完全一样了

Hdu4311 || 4312Meeting point-1/-2 n个点中任意选一个点使得其余点到该点曼哈顿距离之和最小

相关推荐