Cod sursa(job #2240092)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 12 septembrie 2018 15:09:33
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.23 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#define DIM 100005

using namespace std;
struct punct{
    int x;
    int y;
};
punct v[DIM],w[DIM],t[DIM];
int n;
long long modul (long long x){
    if (x<0)
        return -x;
    return x;
}
int cmp (punct a,punct b){
    if (a.x!=b.x)
        return a.x<b.x;
    return a.y<b.y;
}
int cmp2 (punct a,punct b){
    if (a.y!=b.y)
        return a.y<b.y;
    return a.x<b.x;
}
long long calcul (punct i,punct j){
    return (i.x-j.x)*(i.x-j.x) + (i.y-j.y)* (i.y-j.y);
}
void interclas (int st,int mid,int dr){
    int i,j,poz;
    i=st;
    j=mid+1;
    poz=st-1;
    while (i<=mid && j<=dr){
        if (v[i].y<v[j].y || (v[i].y==v[j].y && v[i].x<v[j].x)){
            t[++poz]=v[i];
            i++;
        }
        else {
            t[++poz]=v[j];
            j++;
        }
    }
    while (i<=mid){
        t[++poz]=v[i];
        i++;
    }
    while (j<=dr){
        t[++poz]=v[j];
        j++;
    }
    for (i=st;i<=dr;i++)
        v[i]=t[i];
}
long long combin (int st,int dr,long long sol){
    int mid,px,elem,i,j;
    mid=(st+dr)/2;
    interclas (st,mid,dr);
    px=v[mid].x;
    elem=0;
    for (i=st;i<=dr;i++){
        if (modul((long long)v[i].x-px)<=sol)
            w[++elem]=v[i];
    }
    for (i=1;i<elem;i++){
        for (j=1;j<=7 && i+j<=elem;j++)
            sol=min(sol,calcul(w[i],w[i+j]));
    }
    return sol;
}
long long rec (int st,int dr){
    long long sol=80000000000;
    int i,j,mid;

   // if (st==1 && dr==5)
     //   printf ("a");
    if (dr-st+1<=3){ /// iau 2 cate 2
        for (i=st;i<dr;i++)
            for (j=i+1;j<=dr;j++)
                sol=min(sol,calcul(v[i],v[j]));
    }
    else {
        mid=(st+dr)/2;
        sol=rec (st,mid);
        sol=min(sol,rec (mid+1,dr));
        sol=min(sol,combin (st,dr,sol));
    }
    //printf ("%d %d %lld\n",st,dr,sol);
    return sol;
}
int main()
{
    FILE *fin=fopen ("cmap.in","r");
    FILE *fout=fopen ("cmap.out","w");
    int i;
    fscanf (fin,"%d",&n);
    for (i=1;i<=n;i++)
        fscanf (fin,"%d%d",&v[i].x,&v[i].y);
    sort (v+1,v+n+1,cmp);
    fprintf (fout,"%.6lf",(double)sqrt(rec (1,n)));
    return 0;
}