Pagini recente » Cod sursa (job #1635589) | Cod sursa (job #2186588) | Cod sursa (job #1440838) | Cod sursa (job #546669) | Cod sursa (job #1611070)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int NMAX = 100000;
const int eps = 0.0000001;
typedef long long Tpoint;
int n;
class Point {
public:
Tpoint x; Tpoint y;
Point() : x(0), y(0) { }
Point(Tpoint x, Tpoint y) : x(x) , y(y) { }
};
vector<Point> v;
void read() {
fin >> n ;
for(int i = 1; i <= n; ++i) {
Tpoint x; Tpoint y;
fin >> x >> y;
v.push_back({x, y});
}
}
bool compareX(const Point& a, const Point& b) {
return a.x < b.x;
}
bool compareY(const Point& a, const Point& b) {
return a.y < b.y;
}
double distance(const Point& a, const Point& b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) ;
}
Tpoint mod(Tpoint x) { return x < 0 ? -x : x; }
int lowerBoundX(Tpoint value, vector<Point>& v) {
int pos = 0 ; int step = 1;
for(; step <= n - 1; step <<= 1);
for( ; step ; step /= 2)
if(pos + step <= n - 1 && v[pos + step].x < value)
pos += step;
if(pos < n - 1)
return pos + 1;
return pos;
}
int upperBoundX(Tpoint value, vector<Point>& v) {
int pos = 0 ; int step = 1;
for(; step <= n - 1; step <<= 1);
for( ; step ; step /= 2)
if(pos + step <= n - 1 && v[pos + step].x <= value)
pos += step;
return pos;
}
double findDistance(int st, int dr, vector<Point>& v) {
//la 3 puncte ne oprim
if(dr - st <= 2 ) {
//sunt minim 2
double min1 = distance(v[st], v[st + 1]);
if(st + 2 < n)
return min(min1, distance(v[st + 1], v[st + 2]) );
return min1;
}
int median = st + (dr - st) / 2;
double minD = min(findDistance(st, median, v), findDistance(median + 1, dr, v));
//int leftIndex = lowerBoundX(v[median].x - minD , v);
//int rightIndex = upperBoundX(v[median].x + minD, v);
vector<Point> m;
for(int i = st; i <= dr; ++i)
if( (v[i].x - v[median].x) * (v[i].x - v[median].x) <= minD )
m.push_back(v[i]);
sort(m.begin(), m.end(), compareY);
for(unsigned i = 0 ; i < m.size(); ++i)
for(unsigned j = i + 1; j <= i + 7 && j < m.size(); j++)
minD = min(minD, distance(m[i], m[j]));
return minD;
}
void solve() {
sort(v.begin(), v.end(), compareX);
fout << fixed << setprecision(6) << sqrt(findDistance(0, n - 1, v));
}
int main() {
read();
solve();
return 0;
}