печать ближайшей пары точек

Я писал этот код, чтобы найти минимальное расстояние между двумя точками. Код, который я написал, дает мне правильное минимальное расстояние, но не дает правильных координат, из которых вычисляется минимальное расстояние. Пожалуйста, помогите мне определить проблему в соответствии со мной является правильным подходом для печати точек, а также с минимальным расстоянием.

#include<bits/stdc++.h>
#define FOR(i,N) for(int i=0;i<(N);i++)
#define rep(i,a,n) for(int i=(a);i<(n);i++)
using namespace std;
struct point {
int x;
int y;
};

typedef struct point point;
void printarr(point arr[], int n) {for(int i = 0; i < n; i++) cout <<
arr[i].x << " " << arr[i].y << endl; cout << endl;
bool comparex(const point& X, const point& Y) { return X.x < Y.x; }
bool comparey(const point& X, const point& Y) { return X.y < Y.y; }

float getdis(point X, point Y) { return sqrt((X.x - Y.x)*(X.x - Y.x) + (X.y
- Y.y)*(X.y - Y.y)); }
float brutedis(point P[], int n, point A[]) {
float d = INT_MAX;
float temp;
FOR(i, n) {
rep(j, i+1, n) {
temp = getdis(P[i],P[j]);
if(temp < d) {
d = temp;
A[0].x = P[i].x; A[0].y = P[i].y;
A[1].x = P[j].x ; A[1].y = P[j].y;
}
}
}
return d;
}

float stripdis(point P[], int n, float d, point A[]) {
float temp = d;
float dis;
sort(P, P + n, comparey);
FOR(i, n) {
rep(j,i+1,n) {
if(abs(P[j].y - P[i].y) < d) {
dis = getdis(P[j], P[i]);
if(dis < temp) {
temp = dis;
A[0].x = P[i].x; A[0].y = P[i].y;
A[1].x = P[j].x ; A[1].y = P[j].y;
}
}
}
}
return temp;
}

float solve(point P[], int n, point A[]) {

if(n <= 3) return brutedis(P, n, A);

int mid = n/2;
point M = P[mid];
float d = min(solve(P, mid, A), solve(P+mid, n-mid, A));
point strip[n];
int j = 0;
int i = 0;
while(i < n) {
if(abs(P[i].x - M.x) < d) strip[j++] = P[i];
i++;
}

return min(d, stripdis(strip, j, d, A));
}

int main() {

point P[] = {{0, 0}, {-4,1}, {-7, -2}, {4, 5}, {1, 1}};
int n = sizeof(P) / sizeof(P[0]);
sort(P, P+n, comparex);
point A[2];
cout << "Minimum Distance = " << solve(P, n, A) << "\n";
printarr(A, 2);
//printarr(P, n);
return 0;
}

0

Решение

Ты звонишь solve дважды, и оба дают его в качестве параметра. Каждый из этих вызовов всегда перезаписывает A, но только один возвращает правильный ответ. И они оба называют brutedis, который также всегда перезаписывает A.

Самый простой способ исправить это — ввести дополнительный параметр для всех этих функций, который будет содержать минимальное расстояние, найденное до сих пор, так же, как вы это делали с stripdis.

float solve(point P[], int n, float d, point A[]) {

if(n <= 3) return brutedis(P, n, d, A);

...
d = solve(P, mid, d, A);
d = solve(P+mid, n-mid, d, A);

d = stripdis(strip, j, d, A));

...float brutedis(point P[], int n, float d, point A[])
{
// float d = INT_MAX -- Not needed

Таким образом, A будет переопределен только в том случае, если расстояние между новой парой точек равно глобально пока минимально.

Не нужно звонить min так как каждая функция уже сохраняет минимум d и расстояние, которое он находит.

0

Другие решения

Если я могу следовать вашему плохо отформатированному коду, brutedis безоговорочно изменяет A [], и он вызывается снова после того, как вы нашли правильный ответ (но не знаете, что вы нашли правильный ответ).

Так что, если первый звонок был лучшим в min(solve(P, mid, A), solve(P+mid, n-mid, A)); второй еще может вызвать брутедис и уничтожить А []

1

Это потому, что после получения правильных координат в массиве «A», вы снова обновляете это. просто посмотрите на приведенное ниже утверждение в вашем коде:

float d = min(solve(P, mid, A), solve(P+mid, n-mid, A));

это даст правильное минимальное расстояние, но не правильные координаты. Подумайте об этом, если ваш первый вызов для решения в приведенном выше утверждении имеет координаты минимального расстояния, то ваш второй вызов изменит координаты в A []. возьмите ручку и бумагу и попытайтесь найти координаты, которые у вас есть, это поможет вам лучше понять.

0
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector