Pagini recente » Cod sursa (job #1029869) | Cod sursa (job #3256138) | Rating Botnaru Victor (Botnaru_Victor) | Rezultatele filtrării | Cod sursa (job #1226196)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <vector>
#define INF 1LL * 1000000000 * 1000000000
using namespace std;
typedef struct {
int x;
int y;
} punct;
int N;
punct v[100011];
punct V[100011];
vector <int> indici;
inline int cmp1 (punct a, punct b) {
if (a.x == b.x) return (a.y < b.y);
return (a.x < b.x);
}
inline int cmp2 (punct a, punct b) {
if (a.y == b.y) return (a.x < b.x);
return (a.y < b.y);
}
void Citire () {
ifstream fin ("cmap.in");
fin >> N;
for (int i = 1; i <= N; i++)
fin >> v[i].x >> v[i].y;
fin.close ();
}
long long min (long long A, long long B) {
if (A < B) return A;
return B;
}
long long dist (int i, int j) {
return (1LL * (v[i].x - v[j].x) * (v[i].x - v[j].x) + 1LL * (v[i].y - v[j].y) * (v[i].y - v[j].y));
}
inline int abs (int a) {
if (a >= 0) return a;
return -a;
}
void mergem (int L, int R) {
int mijl = (L + R) / 2;
int i = L;
int j = mijl + 1;
for (; i <= mijl && j <= R;)
{
if (cmp2 (v[i], v[j])) V[i + j - mijl - 1] = v[i], i++;
else V[i + j - mijl - 1] = v[j], j++;
}
for (; i <= mijl; i++)
V[i + j - mijl - 1] = v[i];
for (; j <= R; j++)
V[i + j - mijl - 1] = v[j];
for (int i = L; i <= R; i++)
v[i] = V[i];
}
long long DivQ (int L, int R) {
if (L >= R) return INF;
int mijl = (L + R) / 2;
long long D = min (DivQ (L, mijl), DivQ (mijl + 1, R));
if (R == L + 1) sort (v + L, v + R + 1, cmp2);
else mergem (L, R);
for (int i = L; i <= R; i++)
if (abs (v[i].x - v[mijl].x) <= D) indici.push_back (i);
for (int i = 0; i < (int) indici.size (); i++)
for (int j = i + 1; j <= i + 7 && j < (int) indici.size (); j++)
D = min (D, dist (indici[i], indici[j]));
indici.clear ();
return D;
}
void Scriere () {
ofstream fout ("cmap.out");
fout << fixed << setprecision (6) << sqrt (1.0 * DivQ (1, N));
fout.close ();
}
int main () {
Citire ();
sort (v + 1, v + N + 1, cmp1);
Scriere ();
return 0;
}