Cod sursa(job #1075303)

Utilizator dd1997Dan Vasile dd1997 Data 8 ianuarie 2014 20:32:54
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.41 kb

#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

ifstream f ("cmap.in");
ofstream g ("cmap.out");
struct punct {int x,y;} ;
punct p[100001],pp[100001];

int compx(punct a, punct b)
{
    if (a.x < b.x)
      return 1;
    else
      return 0;
}

int compy(punct a, punct b)
{
    if (a.y < b.y)
      return 1;
    else
      return 0;
}

int n, i, k=1;

double dist(punct a, punct b)
{
    double ax=a.x,bx=b.x,ay=a.y,by=b.y;
    return sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by));
}

double ddcmap(int pst, int pdr)
{
    if (pdr-pst<=2)
        if (pdr-pst == 1)
          return dist(p[pdr],p[pst]);
        else
        {
            double d1 = dist(p[pst],p[pst+1]);
            double d2 = dist(p[pst],p[pdr]);
            double d3 = dist(p[pdr],p[pst+1]);
            return min(min(d1,d2),d3);
        }
    else
    {
        int m= (pst+pdr)/2,i,j;
        double s1 = ddcmap(pst, m);
        double s2 = ddcmap(m+1, pdr);
        double smin = min(s1,s2);
        //vector <punct> v;
        j=0;
        for (i=m+1;i<n;i++)
        {
            if (p[i].x > p[m].x+smin)
              break;
            pp[j++]=p[i];
        }
        int p2 = i-1;
        for (i=m;i>=0;i--)
        {
            if (p[i].x < p[m].x - smin)
              break;
            //v.push_back(p[i]);
            pp[j++]=p[i];
        }
        int p1 = i+1;
        //k++;
        //cout << p[m].x<<' '<<p[p1].x<<' '<<p[p2].x<<' ';
        //cout << smin << ' '<< m-p1+1<<' '<<p2-m+1<<"    ";
        //if (k%200==0)
        //  system("pause");
        sort(pp,pp+j,compy);
        for (i=0;i<j;i++)
          for (int ii=i+1;ii<j && ii<=i+7;ii++)
            {
                double d1 = dist(p[i],p[ii]);
                if(d1<smin)
                    smin=d1;
            }



        //for(int i=p1; i <=m ; i++)
        //for(int j=m+1; j<=p2; j++)
        //{            double d1 = dist(p[i],p[j]);
        //    if(d1<smin)   smin=d1;  }
    return smin;
    }
}


int main()
{
    f >> n;
    for(i=0; i<n; i++)
        f >> p[i].x >> p[i].y;
    sort(p,p+n,compx);
    //for (i=0;i<n;i++)
      //cout << p[i].x << ' ' << p[i].y << "   ";
    double rez = ddcmap(0,n-1);
    g.precision(18);
    g<<rez << endl;
    //cout.precision(18);
    //cout << rez << endl;
    return 0;
}