Pagini recente » Cod sursa (job #1637150) | Cod sursa (job #171481) | Cod sursa (job #1624968) | Cod sursa (job #1800538) | Cod sursa (job #1547189)
#include <cmath>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
const int MAX_NUMBER_OF_POINTS = 100000; //Numarul maxim de puncte
// -1000000000 <= absica , ordonata <= 1000000000
const long long MIN_POINT_VALUE = -1000000000;
const long long MAX_POINT_VALUE = 1000000000;
struct Point
{
long long x,y; //Tipul de date al absicei si al ordonatei
Point (long long x = 0, long long y = 0)
{
this -> x = x;
this -> y = y;
}
} bleft(MIN_POINT_VALUE,MIN_POINT_VALUE), //Punctul din cel mai din stanga colt si cel mai de jos | posibil
tright(MAX_POINT_VALUE,MAX_POINT_VALUE); //Punctul din cel mai din dreapt acolt si cel mai de sus | posibil
long double distance(Point A,Point B)
{
return sqrt( (B.x - A.x)*(B.x - A.x) + (B.y - A.y)*(B.y - A.y)); //distanta euclidiana intre punctele A(xa,ya) si B(xb,yb)
}
const long long MAX_POINT_DISTANCE = distance(bleft, tright); //distanta maxima posibila intre 2 puncte
Point X[MAX_NUMBER_OF_POINTS+1], //In X vom tine punctele sortate dupa x apoi dupa y in caz e egalitate cu x
Y[MAX_NUMBER_OF_POINTS+1]; //In Y vom sorta pe parcurs punctele dupa y ca la mergesort
long double dBCPP(int st,int dr)
{
if( dr - st + 1 > 3)
{
int mij = (st+dr)/2;
long double mins,mind,minm;
mins = dBCPP( st , mij );
mind = dBCPP( mij + 1, dr );
minm = min( mins , mind );
int mergeSize = dr - st + 1;
Point Merged[ mergeSize + 2 ];
merge(Y + st , Y + mij + 1, Y + mij + 1, Y + dr + 1, Merged + 1 , []( Point a, Point b ){ return ( a.y < b.y );} );
copy(Merged+1,Merged+mergeSize+1,Y+st);
for(int i = st ; i <= dr ; i++)
for(int j = 1 ; j <= 7 && i+j <= dr && Y[i+j].y - Y[i].y <= minm ; j++)
minm = min( distance(Y[i] , Y[ i+j]), minm);
return minm;
}
else
{
sort(Y+st,Y+dr+1,[](Point a,Point b){return a.y<b.y;});
long double d = MAX_POINT_DISTANCE;
for(int i = st ; i< dr ; i++)
for(int j = i+1 ; j <= dr; j++)
d = min( distance(X[i], X[j]) , d);
return d;
}
}
int main()
{
int n;
in>>n;
for(int i = 1 ; i <= n ; i++)
in >> X[i].x >> X[i].y,
Y[i] = X[i]; //Citim punctele
sort(X+1,X+n+1,[](Point a,Point b) //Sortam punctele din X dupa abscisa apoi dupa ordonata
{
if (a.x < b.x)
return true;
else
{
if (a.x ==b.x)
if (a.y <= b.y)
return true;
else
return false;
return false;
}
});
out<<setprecision(6)<<fixed<<dBCPP(1,n); //afisam distanta intre cele mai apropiate 2 puncte din plan cu 6 zecimale dupa 0
return 0;
}