8725. Closest Point Pair

You are given n points on a plane and your task is to find a pair of points with the smallest euclidean distance between them.

All points will be unique and there is only one pair with the smallest distance.

Input. First line of input will contain n (2 ≤ n ≤ 50000) and then n lines follow each line contains two integers giving the x and y coordinate of the point. Absolute value of x, y will be atmost 10⁶.

Output. Output 3 numbers a b c, where a, b (a < b) are the indexes (0 based) of the point pair in the input and c is the distance between them. Round c to 6 decimal digits.

Sample Input 1	Sample Output 1
5 0 0 0 1 100 45 2 3 9 9	0 1 1.000000
Sample Input 2	Sample Output 2
5 0 0 -4 1 -7 -2 4 5 1 1	0 4 1.414214

РЕШЕНИЕ

геометрия – ближайшая пара

Анализ алгоритма

Реализация алгоритма

#include <cstdio>

#include <cmath>

#include <algorithm>

#define MAX 50010

using namespace std;

struct Point

{

int x, y, id;

};

int Comp_X(const Point &a, const Point &b)

{

return a.x < b.x || a.x == b.x && a.y < b.y;

}

int Comp_Y(const Point &a, const Point &b)

{

return a.y < b.y;

}

Point a[MAX];

double MinDist;

int Ans_a, Ans_b;

void Update_Answer(const Point &a, const Point &b)

{

double Dist = sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + .0);

if (Dist < MinDist)

MinDist = Dist, Ans_a = a.id, Ans_b = b.id;

}

void ClosestPair(int Left, int Right)

{

if (Right - Left <= 3)

{

for (int i = Left; i <= Right; i++)

for (int j = i + 1; j <= Right; j++)

Update_Answer(a[i], a[j]);

sort(a + Left, a + Right + 1, Comp_Y);

return;

}

int Middle = (Left + Right) >> 1;

int MidX = a[Middle].x;

ClosestPair(Left, Middle);

ClosestPair(Middle + 1, Right);

int Len = Right - Left + 1;

Point *temp = new Point[Len];

merge(a + Left, a + Middle + 1, a + Middle + 1, a + Right + 1, temp, Comp_Y);

copy(temp, temp + Len, a + Left);

int TempSz = 0;

for (int i = Left; i <= Right; i++)

if (abs(a[i].x - MidX) < MinDist)

{

for (int j = TempSz - 1; (j >= 0) && (a[i].y - temp[j].y < MinDist); j--)

Update_Answer(a[i], temp[j]);

temp[TempSz++] = a[i];

}

delete[] temp;

}

int i, n;

int main(void)

{

scanf("%d", &n);

for (i = 0; i < n; i++)

{

scanf("%d %d", &a[i].x, &a[i].y);

a[i].id = i;

}

sort(a, a + n, Comp_X);

MinDist = 1E20;

ClosestPair(0, n - 1);

if (Ans_a > Ans_b) swap(Ans_a, Ans_b);

printf("%d %d %.6lf\n", Ans_a, Ans_b, MinDist);

return 0;

}