Question

Se dă o mulțime de puncte în plan. Să se calculeze cea mai mică distanță dintre oricare 2 puncte posibile. In Pascal va rog

Answer 1

// A divide and conquer program in C/C++ to find the smallest distance from a// given set of points.
#include <stdio.h>#include <float.h>#include <stdlib.h>#include <math.h>
// A structure to represent a Point in 2D planestruct Point{ int x, y;};
/* Following two functions are needed for library function qsort().Refer: http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/ */
// Needed to sort array of points according to X coordinateint 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 coordinateint 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 pointsfloat 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 nfloat 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 valuesfloat 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 timesfloat 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 coordinatefloat 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 functionsint main(){ Point P[] = {{2, 3}, {12, 30}}; int n = sizeof(P) / sizeof(P[0]); printf("The smallest distance is %f ", closest(P, n)); return 0;}

Answer 2

program Geometrie;

type punct=record
  x,y:real;
end;
type vec_real=array[1..1000] of real;
var 
   marcaj:array[1..30] of punct;
   distanta:vec_real;
   fisierIntrare:string;
   nr_puncte,nr_distante:integer;
   tfIn:Text;
procedure citire(nume:string;var n:integer);
var i:integer;
    x:real;
begin
  AssignFile(tfIn,nume);
  reset(tfIn);
  read(tfIn,n);
  //n:=round(x);
  for i:=1 to n do
  begin
  read(tfIn,marcaj[i].x);
  read(tfIn,marcaj[i].y);
  end;
end;

function distanta_puncte(p1,p2:punct):real;
begin
distanta_puncte:=sqrt(power(p2.y-p1.y,2)+power(p2.x-p1.x,2))
end;

function min_vector(v:vec_real;n:integer):real;
var i:integer;
    min:real;
begin
   min:=10e15;
   for i:=1 to n do
   begin
      if v[i]<min then
         min:=v[i];
   end;
   min_vector:=min;
end;

//procedure scrie();
//var i:integer;
//    
//begin
//   for i:=1 to nr_puncte do
//   begin   
//   write(marcaj[i].x);
//   write(' ');
//   write(marcaj[i].y);
//   writeln;
//   end;
//end;
var i,j:integer;
begin
   
   fisierIntrare:='puncte_intrare.txt';
   citire(fisierIntrare,nr_puncte);
   //scrie();
   for i:=1 to nr_puncte-1 do
      for j:=i+1 to nr_puncte do
        begin
        inc(nr_distante);
        distanta[nr_distante]:=distanta_puncte(marcaj[i],marcaj[j]);      
        end;   
   writeln('Distanta minima: ',min_vector(distanta,nr_distante));
end.