Pagini recente » Cod sursa (job #2537965) | Cod sursa (job #2129300) | Cod sursa (job #1049243) | Cod sursa (job #692115) | Cod sursa (job #3239781)
#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 = (int64) 8e18 + 10;
static inline int64 myabs (int64 x) {
if (x < 0) return -x;
return x;
}
struct defPoint {
int64 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;}
};
bool sortY (defPoint A, defPoint B) {return A.y < B.y;}
const int CHECK = 10;
defAnswer divide (int left, int right) {
/**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.dist2 < ret.dist2) ret = aux;
}
}
sort (points + left, 1 + points + right, sortY);
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
int64 mid_x = -myINF;
for (int i = left; i <= mid; i ++)
mid_x = max (mid_x, points[i].x);
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];
/**cout << "\n" << min_dist << "\n";
for (int i = left; i <= right; i ++)
cout << points[i].x << " " << points[i].y << "\n";**/
vector<defPoint> best;
for (int i = left; i <= right; i ++)
if (myabs (mid_x - points[i].x) * myabs (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 ();
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";**/
///out << ret.dist2;
return 0;
}