Pagini recente » Cod sursa (job #1721728) | Cod sursa (job #2810286) | Cod sursa (job #3344338) | Cod sursa (job #861185) | Cod sursa (job #3345919)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <cmath>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
const long long INF = (1LL << 62);
struct Point
{
int x, y;
Point(int xx = 0, int yy = 0): x(xx), y(yy) {}
Point& operator = (const Point &p)
{
x = p.x;
y = p.y;
return *this;
}
inline bool operator < (const Point &p) const
{
return (x < p.x || (x == p.x && y < p.y));
}
friend istream& operator >> (istream& in, Point &p)
{
in >> p.x >> p.y;
return in;
}
};
vector<Point> X, /// X - punctele ordonate crescator dupa x
Y; /// Y - punctele ordonate crescator dupa y
int N;
inline long long Abs(long long x) { return x < 0 ? -x : x; }
inline long long Min(long long x, long long y) { return x < y ? x : y; }
inline void MinSelf(long long &x, long long y) { x = (x < y ? x : y); }
long long Dist(Point &p1, Point &p2)
{
int dx = p1.x - p2.x,
dy = p1.y - p2.y;
return (long long)dx * dx + (long long)dy * dy;
}
/// Interclaseaza Y[st..mid] si Y[mid + 1..dr], iar
/// rezultatul va fi pastrat in Y[st..dr]
void Merge(vector<Point> &Y, int st, int mid, int dr)
{
vector<Point> V;
int i = st, j = mid + 1;
while(i <= mid && j <= dr)
if(Y[i] < Y[j])
V.push_back(Y[i++]);
else
V.push_back(Y[j++]);
while(i <= mid)
V.push_back(Y[i++]);
while(j <= dr)
V.push_back(Y[j++]);
for(i = st; i <= dr; i++)
Y[i] = V[i - st];
}
long long GetMinDist(int st, int dr,
vector<Point> &X, vector<Point> &Y)
{
if(st > dr)
return INF;
if(dr - st <= 2) /// Multimea contine maxim 3 elemente
{
long long dist = INF;
for(int i = st; i < dr; i++)
for(int j = i + 1; j <= dr; j++)
MinSelf(dist, Dist(X[i], X[j]));
sort(Y.begin() + st, Y.begin() + dr + 1); /// Sortam Y[st..dr]
return dist;
}
int mid = st + ((dr - st) >> 1);
long long dist = Min(GetMinDist(st, mid, X, Y),
GetMinDist(mid + 1, dr, X, Y));
Merge(Y, st, mid, dr);
vector<Point> V;
for(int i = st; i <= dr; i++)
if(Abs(Y[i].y - X[mid].x) < dist)
V.push_back(Y[i]);
for(int i = 0; i < (int)V.size() - 1; i++)
for(int j = i + 1; j < (int)V.size() && j - i < 8; j++)
MinSelf(dist, Dist(V[i], V[j]));
return dist;
}
void Read()
{
f >> N;
X.resize(N); Y.resize(N);
for(int i = 0; i < N; i++)
f >> X[i];
}
void SortPoints()
{
sort(X.begin(), X.end());
for(int i = 0; i < N; i++)
Y[i] = Point(X[i].y, X[i].x);
}
void FindDist()
{
double minDist = sqrt(GetMinDist(0, N - 1, X, Y));
g << fixed << setprecision(6) << minDist << '\n';
}
int main()
{
Read();
SortPoints();
FindDist();
f.close();
g.close();
return 0;
}