Pagini recente » Cod sursa (job #1896960) | Cod sursa (job #331133) | simulare-oji-23-02-2024 | Cod sursa (job #2853698) | Cod sursa (job #1016594)
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <algorithm>
using namespace std;
#define NMax 100001
#define infinit 1000000000.0
struct punct
{
int x, y;
};
inline double dist( punct a, punct b )
{
return sqrt( pow(( a.x - b.x ), 2) + pow(( a.y - b.y ), 2) );
}
int n; punct v[NMax], aux[NMax];
void interclasare(int li, int mid, int ls)
{
int i = li, j = mid + 1, k = 0;
while (i <= mid && j <= ls)
{
if (v[i].y <= v[j].y)
{
aux[k++] = v[i++];
}
else
{
aux[k++] = v[j++];
}
}
while (i <= mid)
{
aux[k++] = v[i++];
}
while (j <= ls)
{
aux[k++] = v[j++];
}
for (int i = li; i<=ls; i++)
v[i] = aux[i-li];
}
int compare1(void const *a, void const *b)
{
punct * _a = (punct*)a; punct * _b = (punct*)b;
return (_a->y - _b->y);
}
double DivideEtImpera(int li, int ls)
{
if (ls - li == 0)
{
return infinit;
}
if (ls - li == 1)
{
return dist(v[ls], v[li]);
}
int mid = (li + ls)/2;
punct midp = v[mid];
double distSt = DivideEtImpera(li, mid);
double distDr = DivideEtImpera(mid + 1, ls);
double distt = (distSt > distDr ? distDr : distSt);
interclasare(li, mid, ls);
//qsort(v+li, ls, sizeof(punct), compare1);
int nr = 0;
for (int i = li; i <= ls; i++)
if (dist(v[i], midp) <= distt)
aux[nr++] = v[i];
double distmin = distt;
for (int i = 0; i < nr; i++)
for (int j = i+1; j < nr && j < i+8; j++)
{
double formula = dist(aux[i], aux[j]);
distmin = (distmin > formula ? formula : distmin);
}
return distmin;
}
int compare(const void *a, const void *b)
{
punct* _a = (punct*)a;
punct* _b = (punct*)b;
if ( _a->x == _b->x)
return _a->y - _b->y;
else
return _a->x - _b->x;
}
int main()
{
FILE *f = fopen("cmap.in", "r");
FILE *g = fopen("cmap.out", "w");
fscanf(f, "%d", &n);
for (int i=0; i<n; i++)
{
fscanf(f, "%d %d", &v[i].x, &v[i].y);
}
qsort(v, n, sizeof(punct), compare);
fprintf(g, "%.6lf\n", DivideEtImpera(0, n-1));
fclose(f); fclose(g);
return 0;
}