首页 > ACM题库 > HDU-杭电 > HDU 3373-Point[解题报告]HOJ
2014
03-16

HDU 3373-Point[解题报告]HOJ

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;
}