Cod sursa(job #2280510)

Utilizator dacianouaPapadia Mortala dacianoua Data 10 noiembrie 2018 18:46:05
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define nmax 100000
#define minv(a,b) a<b?a:b;
#define inf 0x3f3f3f3f
using namespace std;
FILE *fin,*fout;
int n;
struct punct
{
    int x,y;
}a[nmax+1],b[nmax+1];
inline int dist(const int &x1,const int &y1,const int &x2, const int &y2)
{
    return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
}
void quicksort(punct c[],int x,int y)
{
    int i=x,j=y,pivot=c[(y+x)/2].y;
    punct tmp;
    while(i<=j)
    {
        while(c[i].y<pivot)
        i++;
        while(c[j].y>pivot)
        j--;
        if(i<=j)
        {
            tmp=c[i];
            c[i]=c[j];
            c[j]=tmp;
            i++;
            j--;
        }
    }
    if(x<j)
        quicksort(c,x,j);
    if(i<y)
        quicksort(c,i,y);
}
int divide(const int &lower,const int &upper)
{
    int minval=inf;
    if(upper-lower<=2)
        {
            for(int i=lower;i<upper;i++)
            for(int j=i+1;j<=upper;j++)
               minval=minv(minval,dist(a[i].x,a[i].y,a[j].x,a[j].y));
              return minval;
        }
    else
    {
        int d=(upper+lower)/2,gg=0;
        int minval1=divide(lower,d);
        int minval2=divide(d,upper);
        minval=minv(minval2,minval1);
        for(int i=lower;i<=upper;i++)
            if(fabs(a[i].y-a[d].y)<minval && i!=d)
            b[++gg]=a[i];
            quicksort(b,1,gg);
        for(int i=1;i<gg;i++)
            for(int j=i+1;j<=gg && j-i<8;j++)
                minval=minv(dist(a[i].x,a[i].y,a[j].x,a[j].y),minval);
        return minval;
    }
}
int main()
{
    fin=fopen("cmap.in","r");
    fout=fopen("cmap.out","w");
    fscanf(fin,"%d",&n);
    for(int i=1;i<=n;i++)
        fscanf(fin,"%d %d",&a[i].x,&a[i].y);
    quicksort(a,1,n);
    fprintf(fout,"%f\n",sqrt((double)divide(1,n)));
    return 0;
}