Pagini recente » Profil lalaband | Statistici Teodora Udroiu (teodoradora) | Diferente pentru planificare/sponsori intre reviziile 18 si 28 | Anamaria | Cod sursa (job #2072669)
#include <stdio.h>
#include <float.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
using namespace std;
struct Point
{
long long x, y;
};
int compareX(const Point &p1, const Point &p2)
{
return p1.x < p2.x;
}
int compareY(const Point &p1, const Point &p2)
{
return p1.y < p2.y;
}
long double dist(Point p1, Point p2)
{
return sqrt( (p1.x - p2.x)*(p1.x - p2.x) +
(p1.y - p2.y)*(p1.y - p2.y)
);
}
long double bruteForce(Point P[], long long n)
{
long double min = LDBL_MAX; // valoarea maxima pentru lonbg double
for (long long i = 0; i < n; ++i)
for (long long j = i+1; j < n; ++j)
if (dist(P[i], P[j]) < min)
min = dist(P[i], P[j]);
return min;
}
long double min(long double x, long double y)
{
return (x < y)? x : y;
}
long double verificaMediana(Point aux[], long long size, long double d)
{
long double min = d;
sort(aux ,aux + size , compareY);
for (long long i = 0; i < size; ++i)
for (long long j = i+1; j < size && (aux[j].y - aux[i].y) < min; ++j)
if (dist(aux[i],aux[j]) < min)
min = dist(aux[i], aux[j]);
return min;
}
long double cautaSolutie(Point *P, int n)
{
if (n <= 3)
return bruteForce(P, n);
int mid = n/2;
Point midPoint = P[mid];
float solutionLeft = cautaSolutie(P, mid);
float solutionRight = cautaSolutie(P + mid, n-mid);
float solutie = min(solutionLeft, solutionRight);
Point aux[n];
int j = 0;
for (int i = 0; i < n; i++)
if (abs(P[i].x - midPoint.x) < solutie )
aux[j] = P[i], j++;
return min(solutie, verificaMediana(aux, j, solutie) );
}
long double closest(Point *P, int n)
{
sort(P, P + n , compareX);
return cautaSolutie(P, n);
}
int main()
{
Point *P;
int n ;
FILE *fin=fopen("cmap.in","r");
FILE *fout=fopen("cmap.out","w");
fscanf(fin , "%d",&n);
P = new Point[n];
for(int i=0;i<n;++i){
long long x,y;
fscanf(fin,"%lld %lld",&x,&y);
P[i].x = x;
P[i].y = y;
}
double d = closest(P, n);
fprintf(fout,"%lf", d);
free(P);
return 0;
}