Threaded Mode | Linear Mode

***drdebcol*** · 01-12-2010, 08:06 AM

Here is one interesting task.
Given N points in K dimensional space (every point has coordinates K), you should find Euclidean distance between two closest points.
Euclidean distance between points A and B in K dimensional space is equal to:
SQRT ((A [1]-B [1]) ^ 2 + (A [2]-B [2]) ^ 2 + ... (A [K]-B [K]) ^ 2)
That is formula for Euclidean distance in n-dimensional space.

Input
The standard input is primarily load two numbers N and K (2 <= N <= 900, 1 <= k <= 50). N is the number of points and K dimension of space. The next N lines load the coordinates of N points, and in each line of K coordinates. Each of the coordinates will be in the range [0..10], and will be given to 3 decimals.

Output
The standard output print a number to 5 decimal, which represents the Euclidean distance between two closest points.

Sample Input
4 2
0,000 0,000
1,000 1,000
2,000 0,000
0,000 2,000

Sample Output
1.41421

Solution
I made a simple function for distance and i went through all dots and i found the smallest.
TPW Code :

Code:

program dots;

uses wincrt;

var

 a:array[1..900,1..50] of 0..10;

 i,j,n,k:integer;

 min,r:real;

function euclidean_distance(x,y:integer):real;

var

  i,j:integer;

  p:real;

begin

  p:=0;

  for i:=1 to k do

    p:=p+sqr(a[x,i]-a[y,i]);

  euclidean_distance:=sqrt(p);

end;

begin

readln(n,k);

for i:=1 to n do

  for j:=1 to k do

    read(a[i,j]);

min:=euclidean_distance(1,2);

for i:=1 to n do

  for j:=i+1 to n do

      begin

        r:=euclidean_distance(i,j);

        if (r<min) then

          min:=r;

      end;

writeln(min:10:5);         

end.

And C++ code :

Code:

# include <iostream>

# include <cstdio>

# include <math.h>

using namespace std;

short a [900][50];

short n,k;

float euclidean_distance(short x, short y)

{

  short i,j;

  float p;

  p=0;

  for (i=0;i<k;i++)

    p+=(a[x][i]-a[y][i])*(a[x][i]-a[y][i]);

  return sqrt(p);

}

int main()

{

    cin>>n>>k;

    short i,j;

    for (i=0;i<n;i++)

      for (j=0;j<k;j++)

        cin>>a[i][j];

    float min,r;

    min=euclidean_distance(1,2);

    for (i=0;i<n;i++)

     for (j=i+1;j<n;j++)

      {

        r=euclidean_distance(i,j);

        if (r<min)

          min=r;

      }

    cout<<min<<endl; 

    system("pause");

}