Pagini recente » Istoria paginii utilizator/xeress | Cod sursa (job #473864) | Cod sursa (job #264006) | Cod sursa (job #2337108) | Cod sursa (job #664192)
Cod sursa(job #664192)
#include <cstdio>
#include <algorithm>
#include <math.h>
#define MAX 100050
using namespace std;
int n, p[MAX];
struct punct
{
int x, y;
}v[MAX];
bool cmpx(punct a, punct b)
{
return a.x < b.x;
}
bool cmpy(int a, int b)
{
return v[a].y < v[b].y;
}
double distanc(int i , int j)
{
double dist;
dist = (v[i].x - v[j].x) * (v[i].x - v[j].x);
dist += (v[i].y - v[j].y) * (v[i].y - v[j].y);
return sqrt(dist);
}
void citire()
{
freopen("cmap.in", "r", stdin);
scanf("%d\n", &n);
for(int i = 1; i <= n; i++)
{
scanf("%d %d\n", &v[i].x, &v[i].y);
}
fclose(stdin);
}
double min(double a, double b)
{
if(a < b)
return a;
return b;
}
double solve(int left, int right)
{
double minimumDistance;
if(right - left + 1 <= 3)
{
minimumDistance = distanc(left, right);
if(right - left == 2)
{
minimumDistance = min(minimumDistance, distanc(left + 1, right));
minimumDistance = min(minimumDistance, distanc(left, left + 1));
}
return minimumDistance;
}
int mij = (left + right) / 2;
minimumDistance = min(solve(left, mij), solve(mij + 1, right));
int k = 1;
for(int i = left; i <= right; i++)
{
if(abs(v[i].x - v[mij].x) <= minimumDistance)
{
p[k++] = i;
}
}
sort(p + 1, p + k, cmpy);
for(int i = 2, j = 1; i < k; i++)
{
while(v[ p[i]].y - v[ p[j]].y >= minimumDistance)
j++;
for(int h = j; h < i; h++)
{
minimumDistance = min(minimumDistance, distanc(h, i));
}
}
return minimumDistance;
}
void afisare()
{
freopen("cmap.out", "w", stdout);
printf("%.6lf", solve(1, n));
fclose(stdout);
}
int main()
{
citire();
sort(v + 1, v + n + 1, cmpx);
afisare();
return 0;
}