Wyznaczanie punktów, które leżą najbliżej siebie

Hej, przygotowałem program, który losuje punkty x, y z zakresu od 0 do 200 i następnie zapisuje je do tablicy. Teraz pytanie jak przeprowadzić operację na tablicach by wyznaczyć punkty, które leżą najbliżej siebie?

Kod poniżej:

#include <iostream>
#include <ctime>
#include <cstdlib>


using namespace std;

int main()
{
srand(time(NULL));

int x, y; // zmienne - punkty, którym pyrzpiszemy wylosowane wartosci

int tablica_X[100]; // punkt x
int tablica_Y[100]; // punkt y

int a = 0; 		// przedzial od
int b = 200;	// przedzial do

/* Losowanie 100 punktow x, y i zapis do tablicy */
for (int i = 0; i<100; i++)
{
x = rand() % b + a;
y = rand() % b + a;
tablica_X[i] = x;
tablica_Y[i] = y;
}

/* Wyswietlanie 100 elementow tablicy */
for (int i = 0; i < 100; i++)
printf("%d %d\n", tablica_X[i],tablica_Y[i]);

return 0;
}

Ale co to są dla ciebie punkty które leżą najbliżej siebie? Chcesz znaleźć parę punktów kóre są sobie najbliższe? Czy może chcesz wszystkie punkty podzielić na klastry jakieś?

Shalom napisał(a):

Ale co to są dla ciebie punkty które leżą najbliżej siebie? Chcesz znaleźć parę punktów kóre są sobie najbliższe? Czy może chcesz wszystkie punkty podzielić na klastry jakieś?

chcę parę punktów kóre są sobie najbliższe

Można by posortować je "Pitagorasem" względem odległości od środka układu współrzędnych (bez pierwiastkowania, bo w tym przypadku to zbędna operacja), i sprawdzać kolejne pary wg stosownego wzoru.

Nic nie napisałeś o wymaganej złożoności, więc przeleć się dwoma pętlami po tablicy i oblicz odległość między każdymi dwoma punktami. Zapamiętaj wartość, która jest najmniejsza.

Szukając "closest pair of points algorithm" znajdziesz:

• http://www.geeksforgeeks.org/closest-pair-of-points/ - O(n x (Logn)^2)
• https://en.wikipedia.org/wiki/Closest_pair_of_points_problem - O(n log n)
• http://www.geeksforgeeks.org/closest-pair-of-points-onlogn-implementation/ - O(n log n)

Skoro będzie 100 punktów, to

   #include<iostream>
   using namespace std;


   int main()
   {
    for (int i = 0; i < 99; i++)
        for (j = i + 1; j < 100; j++)
            // tu porównanie punktów i oraz j, wraz z pamiętaniem minimum
   }

Wykorzystałem Wasze rady i postanowiłem je wdrożyć u siebie, niestety bez skutku. Cały czas pokazuje wartość 0.00.
Polecenie miało jeszcze informację o zaokrągleniu liczb do dwóch miejsc po przecinku stąd float'y

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cmath>

using namespace std;

int main()
{
srand(time(NULL));

float x, y; // zmienne - punkty, którym pyrzpiszemy wylosowane wartosci

float tablica_X[100]; // punkt x
float tablica_Y[100]; // punkt y

int a = 0; 		// przedzial od
int b = 200;	// przedzial do

float odleglosc;
/* Losowanie 100 punktow x, y i zapis do tablicy */
for (int i = 0; i<100; i++)
{
x = rand() % b + a;
y = rand() % b + a;
tablica_X[i] = x;
tablica_Y[i] = y;
}

/* Wyswietlanie 100 elementow tablicy */
for (int i = 0; i < 100; i++)
printf("%.2f %.2f\n", tablica_X[i],tablica_Y[i]);

cout << " " << endl;

float najmniejsza_odleglosc;
float wynik[100];
najmniejsza_odleglosc = wynik[0];

for (int i = 0; i < 99; i++){
	for (int j = i + 1; j < 100; j++){
	
	/* Obliczanie odleglosci punktow A i B */	
	odleglosc = sqrt((tablica_X[j]-tablica_X[i])*(tablica_X[j]-tablica_X[i])+(tablica_Y[j]-tablica_Y[i])*(tablica_Y[j]-tablica_Y[i]));	
	wynik[i] = odleglosc;
	
	/* Zapisywanie najmniejszej odleglosci */
	if(wynik[i] < najmniejsza_odleglosc)
         najmniejsza_odleglosc = wynik[i];

	}	
}
        printf("Najmniejsza odleglosc to %.2f \n", najmniejsza_odleglosc);


return 0;
}

float wynik[100];
najmniejsza_odleglosc = wynik[0];

Masz undefined behaviour, bo nie zainicjalizowałeś wartości w tablicy wynik.

Poza tym nie trzeba używać sqrt(), bo porównanie kwadratów odległości da to samo, ale będzie o parę znaków krócej.
I absolutnie nie wiem, do czego jest tablica wynik, bo ona jest zupełnie bezużyteczna w środku tej podwójnej pętli.

sqrt dopiero na wyniku, dla większe / mniejsze nie ma znaczenia czy liczysz na odległościach czy też ich kwadratach. Dodatkowo https://4programmers.net/Forum/C_i_C++/257074-porownywanie_floatow dla sprawdzania czy masz mniejszą odległość od dotychczasowej

IMO metoda kubełkowa znacznie poprawi wydajność programu, ale to ma sens dla +1000 punktów.