Pagini recente » Cod sursa (job #2755794) | Cod sursa (job #141219) | Cod sursa (job #1929116) | Cod sursa (job #503021) | Cod sursa (job #1547209)
#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) //Distanta intre cele mai apropiate puncte din plan
{
if( dr - st + 1 > 3) //Daca |P| > 3 atunci
{
int mij = (st+dr)/2; //Impartim pe P in 2 jumatati egale
long double mins,mind,minm; //
mins = dBCPP( st , mij ); //luam minimul din partea stanga
mind = dBCPP( mij + 1, dr ); //si din partea dreapta
minm = min( mins , mind ); //si luam nimimul acestor 2 minime
int mergeSize = dr - st + 1; //ne trebuie valoarea lui |P| pentru a stii dimensiunea sirului unde v om avea sortate punctele
Point Merged[ mergeSize + 2 ]; //dupa Y
/*
Deoarece am iesit dintr-o recursivitate unde am sortat crescator dupa y inainte pozitiile st...mij din Vectorul Y si pozitiile mij+1..dr
tot ce trebuie sa facem pentru a avea Y sortat complet trebuie sa interclasam sirurile sortate Y[st..mij] si Y[mij+1,dr]
si o facem folosind procedura merge
pointer catre prima valoare ce trb luata in calcult pt primu interval si pointer catre ultima valoare+1 din acel prim interval
apoi la fel pt al doilea interval si Merged+1 vectoru unde tinem valorile sortate crescator
*/
merge(Y + st , Y + mij + 1, Y + mij + 1, Y + dr + 1, Merged + 1 , []( Point a, Point b ){ return ( a.y < b.y );} );
//copiem valorile din Merged inapoi in Y
copy(Merged+1,Merged+mergeSize+1,Y+st);
//Ficare punct
for(int i = st ; i <= dr ; i++)//Pentru fiecare punct din Y
for(int j = 1 ; j <= 7 && i+j <= dr && Y[i+j].y - Y[i].y <= minm ; j++)//luam urmatoarele 7 cat timp diferenta dintre cel din Y cele urmatoare este <= minm
minm = min(distance(Y[i] , Y[ i+j]), minm);
return minm;
}
else
{
for( int i = st ; i<= dr ; i++)
Y[i] = X[i];
sort(Y+st,Y+dr+1,[](Point a,Point b){return a.y<b.y;});// Sortam punctele Y[st..dr]
long double d = MAX_POINT_DISTANCE; // tinem in d distanta maxima posibila
for(int i = st ; i< dr ; i++)
for(int j = i+1 ; j <= dr; j++)
d = min( distance(X[i], X[j]) , d); //aflam in d distanta minima posibila pentru punctele din X[st...dr]
return d;
}
}
int main()
{
int n;
in>>n;
for(int i = 1 ; i <= n ; i++)
in >> X[i].x >> X[i].y;
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;
}