Pagini recente » Cod sursa (job #514557) | Cod sursa (job #666822) | Cod sursa (job #1836988) | Cod sursa (job #1783081) | Cod sursa (job #1813184)
#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iomanip>
using namespace std;
class punct{
public:
int64_t x;
int64_t y;
bool operator <(const punct p2) const
{
if(x<p2.x)
return 1;
else
if(x>p2.x)
return 0;
if(y<p2.y) //daca au abscisele egale sortam dupa y
return 1;
return 0;
}
};
float compareY(const punct a, const punct b)
{
return (a.y < b.y);
}
punct v[100005];
int N;
int64_t pldist(punct p1, punct p2)
{
return /*sqrt*/( (p1.x - p2.x)*(p1.x - p2.x) +
(p1.y - p2.y)*(p1.y - p2.y) );
}
float brutu(punct p[], int n)
{
int64_t minim = 4e18;
for (int i = 0; i < n; ++i)
for (int j = i+1; j < n; ++j)
if (pldist(p[i], p[j]) < minim)
minim = pldist(p[i], p[j]);
return minim;
}
int64_t minfasie(punct fasie[], int sz, int64_t dist)
{
int64_t minim = dist;
sort(fasie, fasie+sz, compareY);
for (int i = 0; i < sz; ++i)
for (int j = i+1; j < sz && (fasie[j].y - fasie[i].y) < minim; ++j)
if (pldist(fasie[i],fasie[j]) < minim)
minim = pldist(fasie[i], fasie[j]);
return minim;
}
int64_t div_and_q(punct p[], int n)
{
if(n<4)
return brutu(p, n);
int mid = n/2;
punct mijloc = p[mid]; //puncti prin care ducem o || la Oy
int64_t dl = div_and_q(p, mid);
int64_t dr = div_and_q(p + mid, n-mid);
int64_t dist = min(dl, dr);
punct fasie [n];
int j = 0;
for (int i = 0; i < n; i++)
if (abs(p[i].x - mijloc.x) < dist)
{
fasie[j] = p[i];
++j;
}
return min(dist, minfasie(fasie, j, dist));
}
int main()
{
ifstream in ("cmap.in");
ofstream out ("cmap.out");
int i;
in>>N;
for(i=0;i<N;++i)
in>>v[i].x>>v[i].y;
sort(v, v+N);
out<<fixed<<setprecision(6)<<sqrt(div_and_q(v, N));
in.close();
out.close();
return 0;
}