На множестве точек найти пару с минимальным расстоянием. Оптимизировать алгоритм. Сократить перебор.
Простой алгоритм — перебор всех пар и вычисление расстояния для каждой — работает за O(n^2). Построим алгоритм O(n*log(n))по общей схеме алгоритмов "разделяй-и-властвуй" в виде рекурсивной функции, которой передаётся множество точек; эта рекурсивная функция разбивает это множество пополам, вызывает себя рекурсивно от каждой половины, а затем выполняет какие-то операции по объединению ответов. Операция объединения заключается в обнаружении случаев, когда одна точка оптимального решения попала в одну половину, а другая точка — в другую.
Разбивать множество точек на два будем согласно их x-координатам: фактически мы проводим некоторую вертикальную прямую, разбивающую множество точек на два подмножества примерно одинаковых размеров. Тогда возьмём среднюю после сортировки точку Pm и все точки до неё и саму отнесём к первой половине, а все точки после неё — ко второй половине. Теперь, вызвавшись рекурсивно от каждого из множеств A1 и A2, мы найдём ответы h1 и h2 для каждой из половинок. Возьмём лучший из них: h = min(h1, h2). Теперь надо произвести стадию объединения, т.е. попытаться обнаружить такие пары точек, расстояние между которыми меньше h, причём одна точка лежит в A1, а другая — в A2. Очевидно, что для этого достаточно рассматривать только те точки, которые отстоят от вертикальной прямой раздела не расстояние, меньшее h (множество B). Для каждой точки из множества B надо попытаться найти точки, находящиеся к ней ближе, чем h. Например, достаточно рассматривать только те точки, координата y которых отличается не более чем на h. Более того, не имеет смысла рассматривать те точки, у которых y-координата больше y-координаты текущей точки (множество C(Pi)).
Стадия объединения выглядит следующим образом: построить множество B, которое состоит из точек, x координата которых отличается от вертикальной линии не более, чем на h, отсортировать в нём точки по y-координате, затем для каждой точки Pi в B рассмотреть все точки Pj в C(Pi), которое состоит из точек B, у которых y координата не отличается более, чем на h и каждой пары (Pi, Pj) посчитать расстояние и сравнить с текущим наилучшим расстоянием.
class dot {
public:
int x, y;
dot() : x(0), y(0) {}
dot(int a, int b) : x(a), y(b) {}
};
bool cmp_x (const dot &a, const dot &b)
{
return a.x < b.x || a.x == b.x && a.y < b.y;
}
bool cmp_y (const dot &a, const dot &b)
{
return a.y < b.y;
}
double mindist;
dot ma, mb;
void upd_ans (const dot &a, const dot &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, ma = a, mb = b;
}
std::vector<dot> x;
void rec(int l, int r)
{
int i, j;
if (r - l < 4) {
for (i = l; i <= r; ++i)
for (j = i + 1; j <= r; ++j)
upd_ans (x[i], x[j]);
sort(x.begin() + l, x.begin() + r + 1, cmp_y);
return;
}
int m = (l + r) / 2;
int midx = x[m].x;
rec(l, m);
rec(m + 1, r);
inplace_merge(x.begin() + l, x.begin() + m + 1, x.begin() + r + 1, cmp_y);
vector<dot> t;
for (i = l; i <= r; ++i)
if (abs(x[i].x - midx) < mindist) {
for (j = t.size() - 1; j >= 0 && x[i].y - t[j].y < mindist; --j)
upd_ans (x[i], t[j]);
t.push_back(x[i]);
}
}
void addDot(LPARAM lParam)
{
x.push_back(dot(LOWORD(lParam), HIWORD(lParam)));
}
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
int wmId, wmEvent;
PAINTSTRUCT ps;
HDC hdc;
TCHAR szHello[MAX_LOADSTRING];
LoadString(hInst, IDS_HELLO, szHello, MAX_LOADSTRING);
switch (message)
{
case WM_COMMAND:
wmId = LOWORD(wParam);
wmEvent = HIWORD(wParam);
break;
case WM_PAINT:
hdc = BeginPaint(hWnd, &ps);
{
const int R = 3;
HBRUSH oldBrush = (HBRUSH) SelectObject(hdc, CreateSolidBrush(0));
HPEN oldPen = (HPEN) SelectObject(hdc, CreatePen(0, 1, 0));
for (int i = 0; i < x.size(); ++i) {
DeleteObject(SelectObject(hdc, CreateSolidBrush(RGB(255, 0, 0))));
DeleteObject(SelectObject(hdc, CreatePen(0, 2, RGB(255, 0, 0))));
Ellipse(hdc, x[i].x - R, x[i].y - R, x[i].x + R, x[i].y + R);
}
if (x.size() > 2) {
sort(x.begin(), x.end(), cmp_x);
mindist = 1E20;
rec(0, x.size() - 1);
DeleteObject(SelectObject(hdc, CreateSolidBrush(RGB(255, 255, 255))));
DeleteObject(SelectObject(hdc, CreatePen(0, 2, RGB(255, 255, 255))));
Ellipse(hdc, ma.x - R, ma.y - R, ma.x + R, ma.y + R);
Ellipse(hdc, mb.x - R, mb.y - R, mb.x + R, mb.y + R);
DeleteObject(SelectObject(hdc, CreatePen(0, 2, RGB(255, 255, 255))));
MoveToEx(hdc, ma.x, ma.y, 0);
LineTo(hdc, mb.x, mb.y);
DeleteObject(SelectObject(hdc, oldBrush));
DeleteObject(SelectObject(hdc, oldPen));
}
}
EndPaint(hWnd, &ps);
break;
case WM_LBUTTONUP:
addDot(lParam);
InvalidateRect(hWnd, 0, true);
break;
case WM_DESTROY:
PostQuitMessage(0);
break;
default:
return DefWindowProc(hWnd, message, wParam, lParam);
}
return 0;
}
Ключевые слова:
Минимальное, расстояние, нахождение
