2014
03-16

# Point

There are a lot of points on a plane. We need to find the closest point for each point. To be special, “closest” refers to unusual distance: the distance of two points A, B is defined by this:
Distance (A, B) = max (|Ax � Bx|, |Ay � By|)
Please output the sum of the distances.

The input consists of multiply test cases. The first line of each test case contain one integer, n (2 <= n <= 100000), which is the number of points. Each of the next n lines contains two integer, x, y (0 <= x, y <= 1000000000), indicating the coordinate of a point. Two points might have the same coordinate.

The input consists of multiply test cases. The first line of each test case contain one integer, n (2 <= n <= 100000), which is the number of points. Each of the next n lines contains two integer, x, y (0 <= x, y <= 1000000000), indicating the coordinate of a point. Two points might have the same coordinate.

3
0 0
1 1
3 3

4

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#define INF 1000000001

using namespace std;

int n, d[100010];

typedef struct myNode
{
int x, y, id;
}Node;
Node a[100010];
bool cmpx(const Node aa, const Node b)
{
return aa.x < b.x;
}
inline int abs(int x)
{
return x < 0 ? -x : x;
}
inline int max(int a, int b)
{
return a > b ? a : b;
}
int main()
{
int tmp;
while(scanf("%d",&n) != EOF)
{
for(int i = 0; i < n; ++i)
{
d[i] = INF, a[i].id = i;
}
for(int i = 0; i < n; ++i)
scanf("%d%d",&a[i].x,&a[i].y);
sort(a,a+n,cmpx);

for(int i = 0; i < n; ++i)
{
for(int j = i-1; j >= 0; --j)
{
tmp = abs(a[i].x-a[j].x);
if(tmp >= d[i]) break;
tmp = max(tmp,abs(a[i].y-a[j].y));
if(tmp < d[i]) d[i] = tmp;
}
for(int j = i+1; j < n; ++j)
{
tmp = abs(a[i].x-a[j].x);
if(tmp >= d[i]) break;
tmp = max(tmp,abs(a[i].y-a[j].y));
if(tmp < d[i]) d[i] = tmp;
}
}
long long res(0);
for(int i = 0; i < n; ++i)
res += d[i];
printf("%I64d\n",res);
}
return 0;
}