Pagini recente » Borderou de evaluare (job #345061) | Borderou de evaluare (job #1531321) | Borderou de evaluare (job #2813130) | Borderou de evaluare (job #2012157) | Cod sursa (job #2411556)
#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;
set < int > 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;
}
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 * (Vect[i].x - Vect[st].x) * (Vect[i].x - Vect[st].x) >= minDist)
{
Arg.erase(st);
++st;
}
for(auto dot = Arg.begin(); dot != Arg.end();)
{
long long dist = coordDist(Vect[*dot], Vect[i]);
if(minDist > dist)
minDist = dist;
++dot;
}
Arg.insert(i);
}
out << fixed << setprecision(16) << sqrt(minDist) << '\n';
return 0;
}