Cod sursa(job #1075246)

Utilizator dd1997Dan Vasile dd1997 Data 8 ianuarie 2014 19:30:25
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>

using namespace std;

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

int operator < (punct a, punct b)
{
    if (a.x < b.x)
      return 1;
    else
      return 0;
}
/*
int comp(punct a, punct b)
{
    if (a.x < b.x)
      return 1;
    else
      return 0;
}
*/
int n, i;

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;
        double s1 = ddcmap(pst, m);
        double s2 = ddcmap(m+1, pdr);
        double smin = min(s1,s2);
        for (i=m;i<n;i++)
        {
            if (p[i].x > p[m].x+smin)
              break;
        }
        int p2 = i-1;
        for (i=m;i>=0;i--)
        {
            if (p[i].x < p[m].x - smin)
              break;

        }
        int p1 = i+1;
        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);
    //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;
}