Cod sursa(job #1775505)

Utilizator Mihaibv13Mihai Stoian Mihaibv13 Data 10 octombrie 2016 15:14:56
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int a[100001],b[100001],c[100001],d[100001];



double distanta(int x1,int y1,int x2,int y2)
{
    return sqrt((long long)(x1-x2)*(x1-x2)+(long long)(y1-y2)*(y1-y2));
}

double dist(int li,int lf)
{
    double aa,bb;
    double mn;
    int nr=lf-li+1;
    if(nr==2)
        return distanta(c[li],d[li],c[lf],d[lf]);
    if(nr==3)
    {
        double segmin=distanta(c[li],d[li],c[li+1],d[li+1]);
        double l=distanta(c[li],d[li],c[lf],d[lf]);
        if(l<segmin) segmin=l;
        l=distanta(c[li+1],d[li+1],c[lf],d[lf]);
        if(l<segmin) segmin=l;
        return segmin;
    }
    int m=(li+lf)/2;
    aa=dist(li,m);
    bb=dist(m+1,lf);
    if(aa<bb) mn=aa;
    else mn=bb;
    int i,j;
    double x=(c[m]+c[m+1])/2;
    double tz;
    for(i=li;i<=m;i++)
    {
        if(x-c[i]<mn)
            for(j=m+1;j<=lf;j++)
            {
                if(c[j]-x<mn)
                {
                    tz=distanta(c[i],d[i],c[j],d[j]);
                    if(tz<mn)
                        mn=tz;
                }
            }
    }
    return mn;
}

int main()
{
    FILE *f=fopen("cmap.in","r");
    FILE *g=fopen("cmap.out","w");
    int i,n;
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++)
        fscanf(f,"%d%d",&a[i],&b[i]);
    sort(a+1,a+n+1);
    fprintf(g,"%.6f",dist(1,n));
    return 0;
}