Pagini recente » Borderou de evaluare (job #475178) | Borderou de evaluare (job #992440) | Borderou de evaluare (job #175528) | Borderou de evaluare (job #1971284) | Cod sursa (job #2411553)
#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);
long long minDist = INF;
Arg.insert(0);
int st = 0; /// go from the left i guess??
for(int i = 1; i < N; ++i)
{
while(coordDist(Vect[st], Vect[i]) >= 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;
}