Задачата е следната:Имаме n  точки в равнина,зададени с координати.Да се намери двойка точки,между които разстоянието е най малко.

Ето и кода до който стигнах но не работи

 

#include <stdio.h>
#include <float.h>
#include <stdlib.h>
#include <math.h>

// A structure to represent a Point in 2D plane
struct Point
{
    int x, y;
};

/* Following two functions are needed for library function qsort().
 

// Needed to sort array of points according to X coordinate
int compareX(const void* a, const void* b)
{
    Point *p1 = (Point *)a, *p2 = (Point *)b;
    return (p1->x - p2->x);
}
// Needed to sort array of points according to Y coordinate
int compareY(const void* a, const void* b)
{
    Point *p1 = (Point *)a, *p2 = (Point *)b;
    return (p1->y - p2->y);
}

// A utility function to find the distance between two points
float dist(Point p1, Point p2)
{
    return sqrt( (p1.x - p2.x)*(p1.x - p2.x) +
                (p1.y - p2.y)*(p1.y - p2.y)
            );
}

// A Brute Force method to return the smallest distance between two points
// in P[] of size n
float bruteForce(Point P[], int n)
{
    float min = FLT_MAX;
    for (int i = 0; i < n; ++i)
        for (int j = i+1; j < n; ++j)
            if (dist(P, P[j]) < min)
                min = dist(P, P[j]);
    return min;
}

// A utility function to find minimum of two float values
float min(float x, float y)
{
    return (x < y)? x : y;
}

// A utility function to find the distance beween the closest points of
// strip of given size. All points in strip[] are sorted accordint to
// y coordinate. They all have an upper bound on minimum distance as d.
// Note that this method seems to be a O(n^2) method, but it's a O(n)
// method as the inner loop runs at most 6 times
float stripClosest(Point strip[], int size, float d)
{
    float min = d; // Initialize the minimum distance as d

    qsort(strip, size, sizeof(Point), compareY);

    // Pick all points one by one and try the next points till the difference
    // between y coordinates is smaller than d.
    // This is a proven fact that this loop runs at most 6 times
    for (int i = 0; i < size; ++i)
        for (int j = i+1; j < size && (strip[j].y - strip.y) < min; ++j)
            if (dist(strip,strip[j]) < min)
                min = dist(strip, strip[j]);

    return min;
}

// A recursive function to find the smallest distance. The array P contains
// all points sorted according to x coordinate
float closestUtil(Point P[], int n)
{
    // If there are 2 or 3 points, then use brute force
    if (n <= 3)
        return bruteForce(P, n);

    // Find the middle point
    int mid = n/2;
    Point midPoint = P[mid];

    // Consider the vertical line passing through the middle point
    // calculate the smallest distance dl on left of middle point and
    // dr on right side
    float dl = closestUtil(P, mid);
    float dr = closestUtil(P + mid, n-mid);

    // Find the smaller of two distances
    float d = min(dl, dr);

    // Build an array strip[] that contains points close (closer than d)
    // to the line passing through the middle point
    Point strip[n];
    int j = 0;
    for (int i = 0; i < n; i++)
        if (abs(P.x - midPoint.x) < d)
            strip[j] = P, j++;

    // Find the closest points in strip. Return the minimum of d and closest
    // distance is strip[]
    return min(d, stripClosest(strip, j, d) );
}

// The main functin that finds the smallest distance
// This method mainly uses closestUtil()
float closest(Point P[], int n)
{
    qsort(P, n, sizeof(Point), compareX);

    // Use recursive function closestUtil() to find the smallest distance
    return closestUtil(P, n);
}

// Driver program to test above functions
int main()
{
    Point P[] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
    int n = sizeof(P) / sizeof(P[0]);
    printf("The smallest distance is %f ", closest(P, n));
    return 0;
}

И като е брут форс, що ги сортираш ?

Правиш масив от пойнтс и го обхождаш с два индекса. Единия индекс се променя от нула до ен минус две, а другия се променя от първия плюс едно до ен минус едно.

Проверяваш каква е дистанцията последователно между всеки две точки, което гореописаното обхождане гарантира, като в една променлива пазиш текущото минимално разстояние, а други две индекс променливи пазят индексите на точките между които е измерено текущото минимално разстояние.

И накрая като завърши брут форс цикъла в съответните променливи имаш минималното разстояние и индексите на точките, между които е измерено

Редактирано 30 март 20179 г. от Реджеп Иведик (преглед на промените)

Не ги сортира ами ги разделя на по-малки групи от близки точки за да намали сложността на изчислението от O(n²)

Само че като оставим настрана незатворения коментар /* Following two functions are needed for library function qsort().

и че макар да прилича на С програма има използван синтаксис от С++, не мога да разбера защо компилатора ми дава че Point не е дефиниран и приключва с един куп грешки

И аз не мога да си обясня защо ми дава, че Point не е дефиниран

преди 17 минути, Nikolai Mit написа:

И аз не мога да си обясня защо ми дава, че Point не е дефиниран

Може някъде да е изписан с българско о или друга буква. Напиши пойнт на латиница, ама да си сигурен, и след това копирай и пейстни върху всички пойнт в кода.

А ако компилатора ти дава в кой ред е грешката може и само в този ред

Путкарах гу

Като я е изпляскал без таг за код форума е заменил навсякъде [ i ] с таг за наклонен шрифт

Само дето програмата изкарва минималното разстояние ама не за коя двойка точки е.

#include <stdio.h>
#include <float.h>
#include <stdlib.h>
#include <math.h>

// A structure to represent a Point in 2D plane
struct Point
{
    int x,y;
} ;

// Following two functions are needed for library function qsort(). 
 

// Needed to sort array of points according to X coordinate
int compareX(const void* a, const void* b)
{
    Point *p1 = (Point *)a, *p2 = (Point *)b;
    return (p1->x - p2->x);
}
// Needed to sort array of points according to Y coordinate
int compareY(const void* a, const void* b)
{
    Point *p1 = (Point *)a, *p2 = (Point *)b;
    return (p1->y - p2->y);
}

// A utility function to find the distance between two points
float dist(Point p1, Point p2)
{
    return sqrt( (p1.x - p2.x)*(p1.x - p2.x) +
                 (p1.y - p2.y)*(p1.y - p2.y)
            );
}

// A Brute Force method to return the smallest distance between two points
// in P[] of size n
float bruteForce(Point P[], int n)
{
    float min = FLT_MAX;
    for (int i = 0; i < n; ++i)
        for (int j = i+1; j < n; ++j)
            if (dist(P[i], P[j]) < min)
                min = dist(P[i], P[j]);
    return min;
}

// A utility function to find minimum of two float values
float min(float x, float y)
{
    return (x < y)? x : y;
}


// A utility function to find the distance beween the closest points of
// strip of given size. All points in strip[] are sorted accordint to
// y coordinate. They all have an upper bound on minimum distance as d.
// Note that this method seems to be a O(n^2) method, but it's a O(n)
// method as the inner loop runs at most 6 times
float stripClosest(Point strip[], int size, float d)
{
    float min = d; // Initialize the minimum distance as d
    
    qsort(strip, size, sizeof(Point), compareY);

    // Pick all points one by one and try the next points till the difference
    // between y coordinates is smaller than d.
    // This is a proven fact that this loop runs at most 6 times
    for (int i = 0; i < size; ++i)
        for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j)
            if (dist(strip[i],strip[j]) < min)
                min = dist(strip[i], strip[j]);

    return min;
}

// A recursive function to find the smallest distance. The array P contains
// all points sorted according to x coordinate
float closestUtil(Point P[], int n)
{
    // If there are 2 or 3 points, then use brute force
    if (n <= 3)
        return bruteForce(P, n);

    // Find the middle point
    int mid = n/2;
    
    Point midPoint = P[mid];

    // Consider the vertical line passing through the middle point
    // calculate the smallest distance dl on left of middle point and
    // dr on right side
    float dl = closestUtil(P, mid);
    float dr = closestUtil(P + mid, n-mid);

    // Find the smaller of two distances
    float d = min(dl, dr);

    // Build an array strip[] that contains points close (closer than d)
    // to the line passing through the middle point
    Point strip[n];
    int j = 0;
    for (int i = 0; i < n; i++)
        if (abs(P[i].x - midPoint.x) < d)
            strip[j] = P[i], j++;

    // Find the closest points in strip. Return the minimum of d and closest
    // distance is strip[]
    return min(d, stripClosest(strip, j, d) );
}

// The main functin that finds the smallest distance
// This method mainly uses closestUtil()
float closest(Point P[], int n)
{
    qsort(P, n, sizeof(Point), compareX);

    // Use recursive function closestUtil() to find the smallest distance
    return closestUtil(P, n);
}

// Driver program to test above functions
int main()
{
    Point P[] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
    int n = sizeof(P) / sizeof(P[0]);
    printf("The smallest distance is %f ", closest(P, n));
    return 0;
}

 

преди 2 часа, Реджеп Иведик написа:

Правиш масив от пойнтс и го обхождаш с два индекса. Единия индекс се променя от нула до ен минус две, а другия се променя от първия плюс едно до ен минус едно.

Проверяваш каква е дистанцията последователно между всеки две точки, което гореописаното обхождане гарантира, като в една променлива пазиш текущото минимално разстояние, а други две индекс променливи пазят индексите на точките между които е измерено текущото минимално разстояние.

И накрая като завърши брут форс цикъла в съответните променливи имаш минималното разстояние и индексите на точките, между които е измерено

желязна логика
ако разбирах от програмиране, точно това щях да направя, като броят на комбинациите, въпреки че не е от значение, добива вида
[n!-(n-2)!]/2

Не знам за вас, но това ми прилича на код копиран от нета...

Не знам кой ги измисля тези задачи, но задачата е пак неточна.

Когато имаме n точки в Декартова координатна система то ако си съединим мислено се получава граф. И не са точки, а върхове, n върхове. И не разстояние, а ребра.

https://bg.wikipedia.org/wiki/Алгоритъм_на_Дейкстра

Редактирано 30 март 20179 г. от acnekt (преглед на промените)

преди 1 час, дръндю написа:

желязна логика
ако разбирах от програмиране, точно това щях да направя, като броят на комбинациите, въпреки че не е от значение, добива вида
[n!-(n-2)!]/2

По-скоро n*(n-1)/2 , ако точките са 1000000 даже е много от значение, че проверките на разстоянието между всяка с всяка точка ще са 5*10 на 11 степен броя.

преди 6 минути, ined написа:

По-скоро n*(n-1)/2 , ако точките са 1000000 даже е много от значение, че проверките на разстоянието между всяка с всяка точка ще са 5*10 на 11 степен броя.

Затова има K-d tree, octree алгоритми, ама съм сигурен, че ги знаеш тези неща.

преди 1 час, niki292002 написа:

Не знам за вас, но това ми прилича на код копиран от нета...

Е, ся. Много ясно. Но да си поговорим на тема програмиране. 

преди 3 минути, Реджеп Иведик написа:

Е, ся. Много ясно. Но да си поговорим на тема програмиране. 

Дори от нета тва не променя факта,че не работи 

 

преди 1 час, дръндю написа:

желязна логика
ако разбирах от програмиране, точно това щях да направя, като броят на комбинациите, въпреки че не е от значение, добива вида
[n!-(n-2)!]/2

Това е брут форс. Най лесен за имплементиране, но в общия случай брут форс алгоритмите не са подходящи при големи обеми от данни, и се търсят по сложни за имплементация, но с по малка изчислителна сложност алгоритми. Сложността се приема, че има две компоненти, пространство и време.

преди 5 минути, Nikolai Mit написа:

Дори от нета тва не променя факта,че не работи 

 

Колегата каза, че я е подкарал. Виж копирай му кода.

На visual studio 2008 не тръгва 

Сложи и разширение.cpp и я компилирай като C++ програма, Нямам под ръка VS2008, но на Dev-C++ върви.

преди 3 часа, acnekt написа:

Не знам кой ги измисля тези задачи, но задачата е пак неточна.

Когато имаме n точки в Декартова координатна система то ако си съединим мислено се получава граф. И не са точки, а върхове, n върхове. И не разстояние, а ребра.

https://bg.wikipedia.org/wiki/Алгоритъм_на_Дейкстра

Никъде не се казва, че се търси разстояние по ребрата на граф или каквото и да било. Според мен се подразбира линейно разстояние в равнина.