Pagini recente » Cod sursa (job #1229044) | Cod sursa (job #1342621) | Cod sursa (job #2040667) | Cod sursa (job #76427) | Cod sursa (job #2070745)
#include <iostream>
#include <fstream>
#include <math.h>
#include <iomanip>
#include <float.h>
#include <algorithm>
using namespace std;
typedef struct
{
double x, y;
}punct;
int n;
punct P[100], aux[100], inter[100];
void citire()
{
ifstream f("cmap.in");
f >> n;
for(int i = 1; i <= n; i++)
f >> P[i].x >> P[i].y;
f.close();
}
double dist(punct a,punct b)
{
return (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y);
}
bool comp(punct a,punct b)
{
return a.x < b.x;
}
double minim_brut(punct P[], int n)
{
double min = FLT_MAX;
for (int i = 1; i < n; i++)
for (int j = i+1; j <= n; j++)
if (dist(P[i], P[j]) < min)
min = dist(P[i], P[j]);
return min;
}
double minDist(int st, int dr)
{
if(dr-st+1 <= 3)
return minim_brut(P, dr-st+1);
else
{
int mid = (st+dr) / 2;
double centru = P[mid].x;
double delta = min(minDist(st, mid), minDist(mid+1, dr));
int r = 0;
int radDelt = sqrt(delta);
int i, j, k;
i = k = st; j = mid+1;
while(i <= mid && j <= dr)
{
if(P[i].y < P[j].y)
aux[k++] = P[i++];
else
aux[k++] = P[j++];
}
while(i <= mid)
aux[k++] = P[i++];
while(j <= dr)
aux[k++] = P[j++];
for(i = st; i <=dr ; i++)
{
P[i] = aux[i];
if(P[i].x - centru <= radDelt && P[i].x - centru >= -radDelt)
inter[++r] = P[i];
}
for(i = 1; i <= r; i++)
{
j = min(r, i+7);
for(k = i+1; k <= j; k++)
delta = min(delta, dist(inter[i], inter[k]));
}
return delta;
}
}
int main()
{
citire();
sort(P+1 ,P+n+1, comp);
ofstream g("cmap.out");
g << setprecision(6) << fixed << sqrt(minDist(1, n));
g.close();
return 0;
}