Pagini recente » Cod sursa (job #2867969) | Cod sursa (job #2980938) | Cod sursa (job #1004128) | Cod sursa (job #2236405) | Cod sursa (job #3041465)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct
{
double x;
double y;
} coordonate;
int cmp1(const void *x_void,const void *y_void)
{
double ax = ((coordonate *)x_void)->x;
double ay = ((coordonate *)x_void)->y;
double bx = ((coordonate *)y_void)->x;
double by = ((coordonate *)y_void)->y;
if (ay == by)
{
return (int)(ax - bx);
}
else
return (int)(ay - by);
}
double min(coordonate v[], int st, int dr)
{
double minimul, aux;
if (dr - st == 2)
{
minimul = sqrt((v[st].x - v[dr - 1].x) * (v[st].x - v[dr - 1].x) + (v[st].y - v[dr - 1].y) * (v[st].y - v[dr - 1].y));
for (int i = st; i < dr; i++)
{
for (int j = i + 1;j<=dr; j++)
{
aux = sqrt((v[i].x - v[j].x) * (v[i].x - v[j].x) + (v[i].y - v[j].y) * (v[i].y - v[j].y));
if (minimul > aux)
{
minimul = aux;
}
}
}
return minimul;
}
else
if(dr-st==1)
{
return sqrt((v[st].x - v[dr].x) * (v[st].x - v[dr].x) + (v[st].y - v[dr].y) * (v[st].y - v[dr].y));
}
int mij = (st + dr) / 2;
minimul = min(v, st, mij);
aux = min(v, mij+1, dr);
if (aux < minimul){
minimul = aux;
}
int size = dr+1;
coordonate *Y = (coordonate *)malloc(size * sizeof(coordonate));
double dreapta_mijloc = v[mij].x;
int j = 0;
for (int i = st; i <= dr; i++)
{
aux = v[i].x - dreapta_mijloc;
if (aux < 0)
{
aux *= -1;
}
if (aux <minimul)
{
Y[j] = v[i];
j++;
}
}
if(j!=0){
Y=(coordonate *) realloc(Y, (j) * sizeof(coordonate));
qsort(Y, j,sizeof(coordonate), cmp1);
for (int i = 0; i < j - 1; i++)
{
for (int k = i + 1; k < j ; k++)
{
if(k>i+7)break;
aux = sqrt((Y[i].x - Y[k].x) * (Y[i].x - Y[k].x) + (Y[i].y - Y[k].y) * (Y[i].y - Y[k].y));
//printf("a %lf %lf %d b %lf %lf %d c %lf %lf\n",Y[i].x,Y[i].y,i,Y[k].x,Y[k].y,k,aux,dreapta_mijloc);
if (aux < minimul){
minimul = aux;
}
}
}
}
free(Y);
return minimul;
}
int cmp(const void *x_void, const void *y_void)
{
double ax = ((coordonate *)x_void)->x;
double ay = ((coordonate *)x_void)->y;
double bx = ((coordonate *)y_void)->x;
double by = ((coordonate *)y_void)->y;
if (ax == bx)
{
return (int)(ay - by);
}
else
return (int)(ax - bx);
}
int main()
{
int n;
FILE *f = fopen("cmap.in", "r");
fscanf(f, "%d", &n);
coordonate *v = (coordonate *)malloc(n * sizeof(coordonate));
for (int i = 0; i < n; i++)
{
fscanf(f, "%lf%lf", &v[i].x, &v[i].y);
}
qsort(v, n, sizeof(coordonate), cmp);
double a=min(v, 0, n - 1);
free(v);
fclose(f);
printf("%lf",a);
f=fopen("cmap.out","w+");
fprintf(f,"%lf",a);
fclose(f);
return 0;
}