Pagini recente » Cod sursa (job #3211843) | Cod sursa (job #1344698) | Cod sursa (job #1670064) | Cod sursa (job #1851040) | Cod sursa (job #2411566)
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <set>
using namespace std;
#define FILE_NAME "cmap"
ifstream in (FILE_NAME".in");
ofstream out(FILE_NAME".out");
struct punct
{
int x, y;
punct(int _x = 0, int _y = 0)
{
x = _x;
y = _y;
}
bool operator<(punct operand)
{
if(this->x == operand.x)
return this->y < operand.y;
return this->x < operand.x;
}
};
constexpr long long INF = 0x3f3f3f3f3f3f3f3f;
constexpr int MAX_DIM = 100000 + 4;
punct Vect[MAX_DIM];
int N;
struct comp
{
bool operator()(const int &a, const int &b)
{
if(Vect[a].y == Vect[b].y)
return Vect[a].x < Vect[b].x;
return Vect[a].y < Vect[b].y;
}
};
set < int, comp > Arg;
inline
long long coordDist(punct A, punct B)
{
long long distX = A.x - B.x;
distX *= distX;
long long distY = A.y - B.y;
distY *= distY;
return distX + distY;
}
inline
long long square(long long a)
{
return a * a;
}
int main()
{
in >> N;
for(int i = 0; i < N; ++i)
in >> Vect[i].x >> Vect[i].y;
sort(Vect, Vect + N);
int st = 0; /// go from the left i guess??
long long minDist = coordDist(Vect[0], Vect[1]);
Arg.insert(0); Arg.insert(1);
for(int i = 2; i < N; ++i)
{
while(1LL * square(Vect[i].x - Vect[st].x) > minDist)
{
Arg.erase(st);
++st;
}
auto Iter = Arg.begin();
while(Iter != Arg.end() && square(Vect[i].y - Vect[*Iter].y) > minDist)
Iter = Arg.erase(Iter);
Iter = Arg.end();
while(Iter != Arg.begin() && square(Vect[i].y - Vect[*(--Iter)].y) > minDist)
Iter = Arg.erase(Iter);
for(auto dot = Arg.begin(); dot != Arg.end(); ++dot)
{
long long dist = coordDist(Vect[*dot], Vect[i]);
if(minDist > dist)
minDist = dist;
}
Arg.insert(i);
}
out << fixed << setprecision(16) << sqrt(minDist) << '\n';
return 0;
}