Pagini recente » Cod sursa (job #2816374) | Cod sursa (job #7671) | Cod sursa (job #2808849) | Cod sursa (job #2464428) | Cod sursa (job #3239693)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("cmap.in");
ofstream out ("cmap.out");
using int64 = long long;
const int N_MAX = 1e5;
const int64 myINF = 2e18;
struct defPoint {
int x, y;
int64 dist2 (defPoint other) {
int64 dx = x - other.x;
int64 dy = y - other.y;
int64 ret = dx * dx + dy * dy;
return ret;
}
} points[1 + N_MAX], aux[1 + N_MAX];
struct defAnswer {
int64 dist2;
defPoint A, B;
bool operator < (defAnswer other) {return dist2 < other.dist2;}
};
const int CHECK = 10;
defAnswer divide (int left, int right) {
/**cout << left << " " << right << "\n";
for (int i = left; i <= right; i ++) cout << points[i].x << " " << points[i].y << "\n";
cout << "\n\n";**/
if (right - left <= 3) {
defAnswer ret = {myINF, {0, 0}, {0, 0}};
for (int i = left; i < right; i ++) {
for (int j = i + 1; j <= right; j ++) {
defAnswer aux = {points[i].dist2 (points[j]), points[i], points[j]};
if (aux < ret) ret = aux;
}
}
return ret;
}
else {
int mid = left + (right - left) / 2;
defAnswer leftAns = divide (left, mid);
defAnswer rightAns = divide (mid + 1, right);
int64 min_dist = min (leftAns.dist2, rightAns.dist2);
/// left and right side already sorted by y
vector<defPoint> best;
for (int i = left; i <= right; i ++)
if (abs (points[mid].x - points[i].x) <= min_dist)
best.push_back (points[i]);
defAnswer mergeAns = {myINF, {0, 0}, {0, 0}};
int T = best.size ();
for (int i = 0; i < T; i ++)
for (int j = i + 1; j < min (T, i + CHECK); j ++)
if (mergeAns.dist2 > best[i].dist2 (best[j]))
mergeAns = {best[i].dist2 (best[j]), best[i], best[j]};
best.clear ();
int i = left, j = mid + 1, t = left;
while (i <= mid && j <= right) {
if (points[i].y <= points[j].y)
aux[t ++] = points[i ++];
else
aux[t ++] = points[j ++];
}
while (i <= mid)
aux[t ++] = points[i ++];
while (j <= right)
aux[t ++] = points[j ++];
for (int t = left; t <= right; t ++)
points[t] = aux[t];
defAnswer ret = {myINF, {0, 0}, {0, 0}};
if (leftAns < ret) ret = leftAns;
if (rightAns < ret) ret = rightAns;
if (mergeAns < ret) ret = mergeAns;
return ret;
}
}
bool sortX (defPoint A, defPoint B) {return A.x < B.x;}
int main()
{
int n; in >> n;
for (int i = 1; i <= n; i ++)
in >> points[i].x >> points[i].y;
sort (1 + points, 1 + points + n, sortX);
defAnswer ret = divide (1, n);
long double answer = ret.dist2;
answer = sqrt (answer);
out << fixed << setprecision (7) << answer;
///out << ret.A.x << " " << ret.A.y << "\n";
///out << ret.B.x << " " << ret.B.y << "\n";
return 0;
}