На множестве точек найти пару с минимальным расстоянием. Оптимизировать алгоритм. Сократить перебор. Простой алгоритм — перебор всех пар и вычисление расстояния для каждой — работает за 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; }
Ключевые слова:
Минимальное, расстояние, нахождение
|
|||||||