Pagini recente » Cod sursa (job #2367495) | Cod sursa (job #721976) | Cod sursa (job #236522) | Cod sursa (job #18264) | Cod sursa (job #1273835)
//http://www.infoarena.ro/problema/cmap
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
#define x first
#define y second
#define INF 1000000000ll
#defin NMAX 100005
typedef pair<int,int> punct;
int N;
punct P[NMAX], Y[NMAX], Z[NMAX];
double dist(punct A, punct B)
{
return sqrt( (double)(A.x-B.x)*(A.x-B.x) + (double)(A.y-B.y)*(A.y-B.y) );
}
double solve(int st,int dr)
{
//tot if-ul are Theta(1)
if (dr-st <= 2)
{
double dmin=INF;
int i,j;
//iau toate perechile de puncte si calculez distanta dintre ele
//sunt maxim 3 perechi
for (i=st; i<dr; i++)
for (j=i+1; j<=dr; j++)
dmin=min(dmin, dist(P[i], P[j]));
//sortez punctele dupa y, sunt maxim 3 puncte
sort(Y+st, Y+dr+1);
return dmin;
}
int m=(st+dr)/2, i, j, len=0;
double dmin=min(solve(st,m), solve(m+1,dr));//T(n/2) + T(n/2)
//interclasez punctele sortate dupa y
merge(Y+st, Y+m+1, Y+m+1, Y+dr+1, Z);//Theta(n)
/*in Z tin punctele aflate la o distanta mai mica sau egala cu distanta minima
a semiplanului curent fata de cel mai
din dreapta punct al semiplanului*/
copy(Z, Z+dr-st+1, Y+st); //Theta(n)
for (i=st; i<=dr; i++)
if (abs(Y[i].y - P[m].x) <= dmin)
Z[++len]=Y[i];
/*iau doar cele mai apropiate 7 puncte si calculez dinstanta minima
dintre ele*/
for (i=2; i<=len; i++)
for (j=i-1; j>=1 && i-j<=7; j--)
dmin=min(dmin, dist(Z[i], Z[j]));
return dmin;
}
int main()
{
//
ifstream f("cmap.in");
ofstream g("cmap.out");
int i;
f>>N;
for (i=1; i<=N; ++i)
f>>P[i].x>>P[i].y;
//sortez punctele dupa x si la x egal dupa y
sort(P+1,P+N+1);
//imi salvez punstele in format (y,x) pentru sortarea ulterioara dupa y
for (i=1; i<=N; ++i)
Y[i]=make_pair(P[i].y, P[i].x);
g<<setprecision(6)<<fixed<<solve(1,N)<<"\n";
f.close();
g.close();
return 0;
}