Pagini recente » Cod sursa (job #989714) | Istoria paginii arbori | Cod sursa (job #2425379) | Cod sursa (job #1659866) | Cod sursa (job #2034730)
#include <bits/stdc++.h>
#define MAX_N 100000
using namespace std;
typedef long long lint;
const lint sqrInf = 1LL * 4000000000000000000LL;
int n;
struct coord
{
int x, y;
};
coord v[MAX_N + 1];
coord Y[MAX_N + 1];
coord x[MAX_N + 1];
void readFile()
{
ifstream f("cmap.in");
f >> n;
for(int i = 1; i <= n; i ++)
f >> v[i].x >> v[i].y;
f.close();
}
struct cmpY
{
bool operator() (coord a, coord b)
{
if(a.y != b.y)
return a.y < b.y;
return a.x < b.x;
}
};
lint dist(coord a, coord b)
{
lint dx = a.x - b.x;
lint dy = a.y - b.y;
return dx * dx + dy * dy;
}
bool cmp2(coord a, coord b)
{
if(a.y != b.y)
return a.y < b.y;
return a.x < b.x;
}
void mergeSort(int st1, int dr1, int st2, int dr2)
{
int cr = 0;
int i = st1;
int j = st2;
while(i <= dr1 && j <= dr2)
{
int val = cmp2(Y[i], Y[j]);
if(val == 0)
x[++ cr] = Y[i ++];
else
x[++ cr] = Y[j ++];
}
while(i <= dr1)
x[++ cr] = Y[i ++];
while(j <= dr2)
x[++ cr] = Y[j ++];
for(i = st1; i <= dr2; i ++)
Y[i] = x[i - st1 + 1];
}
lint dmin(int st, int dr)
{
//printf("SUNTEM %d %d\n", st, dr);
if(st == dr)
return sqrInf;
if(dr - st + 1 <= 3)
{
sort(Y + st, Y + dr + 1, cmpY());
lint rez = sqrInf;
int i, j;
for(i = st; i <= dr; i ++)
{
for(j = i + 1; j <= dr; j ++)
rez = min(rez, dist(Y[i], Y[j]));
}
// printf("DIN %d %d\n", st, dr);
// printf("RETURN %lld\n", rez);
return rez;
}
int mid = ((st + dr) >> 1);
lint d = min(dmin(st, mid), dmin(mid + 1, dr));
mergeSort(st, mid, mid + 1, dr);///y
int i;
int k = 0;
for(i = st; i <= dr; i ++)
{
if(dist(Y[i], v[mid]) <= d)
x[++ k] = Y[i];
}
int j;
for(i = 1; i <= k; i ++)
{
for(j = i + 1; j <= i + 5 && j <= k; j ++)
d = min(d, dist(x[i], x[j]));
}
// printf("DIN %d %d\n", st, dr);
// printf("rETURN %lld\n", d);
return d;
}
struct cmp
{
bool operator() (coord a, coord b)
{
if(a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}
};
lint rez;
void solve()
{
sort(v + 1, v + n + 1, cmp());
int i;
for(i = 1; i <= n; i ++)
Y[i] = v[i];
rez = dmin(1, n);
}
void printFile()
{
ofstream g("cmap.out");
g << fixed << setprecision(6) << sqrt(rez) << "\n";
g.close();
}
int main()
{
readFile();
solve();
printFile();
return 0;
}