Pagini recente » Borderou de evaluare (job #1516622) | Cod sursa (job #2253375) | Cod sursa (job #2100638)
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct punct
{
int x, y;
} *X,*Y,*LY; /// in v si z punctele , in w punctele la distanta <= d fata de dreapta verticala
int n;
bool cmpX(punct a, punct b)
{
return a.x < b.x;
}
bool cmpY(punct a, punct b)
{
return a.y < b.y;
}
long long dist( punct a, punct b)
{
long long X = 1LL * (a.x - b.x );
long long Y = 1LL * ( a.y - b.y );
return X*X + Y*Y ; /// calculeaza distanta euclidiana la patrat
}
long long divide(int st,int dr,punct y[],int nr)
{
if(dr-st == 1)
return dist( X[st], X[dr] );
if (dr-st == 2)
return min(dist(X[st], X[st+1]),min(dist(X[st+1], X[dr]),dist(X[st], X[dr])));
int mij=(st+dr)/2;
int i,p=0,q=0;
punct *SY = new punct[nr+1];
punct *DY = new punct[nr+1];
for( i = 0; i <= nr; i++)
if( y[i].x < X[mij].x )
{
SY[p].x = y[i].x;
SY[p].y = y[i].y;
++p;
}
else
{
DY[q].x = y[i].x;
DY[q].y = y[i].y;
++q;
}
long long d1 = divide ( st, mij, SY, p-1 ) ;
long long d2 = divide ( mij+1, dr,DY, q-1 ) ;
long long d = min( d1, d2); /// d va fi minimul dintre distanta minima a punctelor din stanga verticalei si distanta minima a punctelor din dreapta ei
long long d_sqrt = ceil(sqrt(d));
int j,k=0;
for( i = 0; i <= nr; i++) /// consideram toate punctele din subproblema actuala
if( abs( y[i].x - X[mij].x ) <= d_sqrt ) /// daca punctul X[i] se afla la distanta <= delta fata de verticala,atunci poate contribui la
{ /// distanta minima a 2 puncte din plan; il adaugam in vectorul w
LY[k].x = y[i].x;
LY[k].y = y[i].y;
k++;
}
for(i = 0; i < k ; i++) /// pentru fiecare punct i consideram alte 7 puncte cu care ar putea avea distanta minima
for(j = i + 1 ; j <= (i+7) && j < k; j++)
d = min(d,dist(LY[i],LY[j])); /// daca distanta dintre LY[i] si LY[j] < distanta minima gasita pana acum,atunci reactualizam distanta minima
delete [] SY;
delete [] DY;
return d;
}
int main()
{
f >> n;
X = new punct[n+1];
Y = new punct[n+1];
LY = new punct[n+1];
for ( int i = 0; i < n ; i++)
{
f >> X[i].x >> X[i].y;
Y[i].x = X[i].x;
Y[i].y = X[i].y;
}
sort(X,X+n,cmpX); /// dupa absicsa
sort(Y,Y+n,cmpY); /// dupa ordonata
g << fixed << setprecision(6) << sqrt(divide(0,n-1,Y,n-1));
delete [] X;
delete [] Y;
delete [] LY;
f.close();
g.close();
return 0;
}