Cod sursa(job #1172782)

Utilizator roxana.istratePoenaru Roxana roxana.istrate Data 18 aprilie 2014 00:07:37
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.1 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
#define nmax 100001
 
struct punct { int x,y;};
 
punct v[nmax];
int n;
 
double cmp(punct p1, punct p2)
{
    return p1.x<=p2.x;
}
double dist (punct p1, punct p2)
{
    return sqrt(pow((double)(p1.x-p2.x),2.0) + pow((double)(p1.y-p2.y),2.0));
}
double distmin(int st, int dr)
{
    if (dr - st <= 2)
    {
        if (dr==st+1)
        {
            double d = dist(v[st], v[dr]);
            //cout<<st<<' '<<dr<<' '<<d<<endl;
            return d;
        }
        if (dr==st+2)
        {
            double mini = dist(v[st],v[st+1]);
            double d2 = dist(v[dr],v[st+1]);
            double d3 = dist(v[st],v[dr]);
            if (mini > d2)
                mini = d2;
            if (mini > d3)
                mini = d3;
            //cout<<st<<' '<<dr<<' '<<mini<<endl;
            return mini;
        }
    }
    else
    {
        int j,i,ls,ld;
        int mj = (st+dr)/2;
        double d = distmin(st,mj);
        double d2 = distmin(mj+1,dr);
        if (d > d2)
            d = d2;
        for (i=mj;i>=st;i--)
            if (v[mj].x - v[i].x > d)
                break;
        ls = i+1;
        for (i=mj+1;i<=dr;i++)
            if (v[i].x - v[mj+1].x > d)
                break;
        ld = i-1;
        for (i=ls;i<=mj;i++)
            for (j=mj+1;j<=ld;j++)
            {
                double d1 = dist(v[i],v[j]);
                if ( d1 < d)
                    d = d1;
            }
        //cout<<st<<' '<<dr<<' '<<ls<<' '<<mj<<' '<<ld<<endl;
        return d;
    }
}
int main()
{
    int i;
    ifstream fin("cmap.in");
    fin>>n;
    for (i=0;i<n;i++)
        {
            fin >> v[i].x>>v[i].y;
            //v[i].x/=100000;
            //v[i].y/=100000;
        }
    sort(v,v+n,cmp);
    //for (i=0;i<n;i++)
    //  cout<<i<<':'<<v[i].x<<' '<<v[i].y<<'\t';
    //cout<<endl;
    //cout<<fixed<<setprecision(6);
    //cout<<distmin(0,n-1)<<endl;
     
    ofstream fout("cmap.out");
     
    fout<<fixed<<setprecision(6);
    fout<<distmin(0,n-1)<<endl;;
     
    return 0;
}