Cod sursa(job #1021468)

Utilizator mariacMaria Constantin mariac Data 3 noiembrie 2013 20:55:46
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.32 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <iomanip>

using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

int minim;
struct punct
{
    int x,y;
};
vector<punct> lista;
vector<punct> s;

bool cmp(punct a, punct b)
{
    return a.x < b.x;
}
bool cmp2(punct a, punct b)
{
    return a.y < b.y;
}
double dist(int x, int y)
{
    return sqrt((lista[x].x - lista[y].x)*(lista[x].x - lista[y].x)+ (lista[x].y - lista[y].y)*(lista[x].y - lista[y].y));
}
double dist1(int x, int y)
{
    return sqrt((s[x].x - s[y].x)*(s[x].x - s[y].x)+ (s[x].y - s[y].y)*(s[x].y - s[y].y));
}
double dmin(int xz, int yz){
   if(yz - xz <= 2 && yz-xz!=0){
                    double ddmin;
                    ddmin = dist(xz,yz);
                    if(xz + 1 < yz) {
                                    double aux;
                                    aux = dist( xz, xz+1);
                                    if(aux < ddmin) ddmin = aux;
                                    aux = dist( xz+1, yz);
                                    if(aux < ddmin) ddmin = aux;
                                }

                    return ddmin;
                }
    else {
            double s1,s2, s0;
            int a,b,c;
            a = (xz + yz)/2;
            c = a;
            b = a+1;
            s1 = dmin( xz, a);
            s2 = dmin( b, yz);
            s0 = s1 < s2 ? s1 : s2;
            while(a > xz && lista[c].x - lista[a].x <= s0  ) s.push_back(lista[a--]);
            while(b < yz && lista[b].x - lista[c].x <= s0) s.push_back(lista[b++]);
            sort(s.begin(), s.end(), cmp2);
            //fout<<s.size();

             for (int i = 0; i < s.size(); ++i)
                for (int j = i + 1; j < s.size() && (j - i) < 8; j++) {
                    {
                      double x;
                      x = dist1(i,j);
                      if( x < s0 && x!=0) s0 = x;
                    }


            }
            s.empty();
            return s0;
    }
}
int main()
{
    int N;

    fin>>N;
    for(int i = 0; i < N; i++)
    {
        punct aux;
        fin>>aux.x>>aux.y;
        lista.push_back(aux);
    }
    sort(lista.begin(), lista.end(), cmp);

    fout<< setprecision(20)<<dmin(0,N-1);
    return 0;
}