Cod sursa(job #1166947)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 3 aprilie 2014 23:51:58
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.16 kb
//Cele mai apropiate puncte din plan
#include<fstream>
#include<algorithm>
#include<iomanip>
#include<cmath>
using namespace std;
typedef struct { int x, y; } punct;
punct a[100005],aux[100005];
int i,j,n;

bool cmp( punct a, punct b){
     if (a.x==b.x) return(a.y<b.y);
      else return(a.x<b.x);
}

bool cmp1( punct a, punct b){ return(a.y<b.y); }

double abss(double x) {
       if (x<0) return(-x);
        else return(x);
}

double dist(punct a, punct b){
       return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}

double solutie(int l, int r) {
    //cazul banal cu 3 sau 2 puncte
    if (  r-l+1<=3 ) {
            double dmin=dist(a[l],a[l+1]);
            for (int i=l; i<r; ++i)
             for (int j=i+1; j<=r; ++j)
              dmin=min(dmin,dist(a[i],a[j]));
            sort(a+l,a+r+1,cmp1);
            return dmin;
            }
    //daca am mai multe puncte le impart in doua submultimi
    int mid=(l+r)/2;
    double xc=(a[mid].x+a[mid+1].x)/2;
    double leftmin=solutie(l,mid), rmin=solutie(mid+1,r);
    double s=min(leftmin,rmin);
    //interclasez partea stinga si partea dreapta in a, care sunt sortate dupa y
    int p1=l, p2=mid+1;
    for (int i=1; i<=(r-l+1); ++i) {
        if (p1<=mid&&p2<=r&&a[p1].y<=a[p2].y) { aux[i]=a[p1]; ++p1; }
         else if (p1<=mid&&p2<=r&&a[p1].y>a[p2].y) { aux[i]=a[p2]; ++p2; }
          else if (p1>mid) { aux[i]=a[p2]; ++p2; }
           else { aux[i]=a[p1]; ++p1; }
           }
    for (int i=l; i<=r; ++i) a[i]=aux[i-l+1]; 
    //acum iau punctele care se afla la distanta maxim s de drapta centrala
    int nraux=0;
    for (int i=l; i<=r; ++i)
     if (abss(a[i].x-xc)<=s) { ++nraux; aux[nraux]=a[i]; } 
    //sortez punctele respective dupa y
   // sort(aux+1,aux+nraux+1,cmp1);
    for (int i=1; i<nraux; ++i) 
     for (int j=i+1; j<=min(i+7,nraux); ++j)
      s=min(s, dist(aux[i],aux[j]));
    return s;
}

int main(void) {
    ifstream fin("cmap.in");
    ofstream fout("cmap.out");
    fin>>n;
    for (i=1; i<=n; ++i) fin>>a[i].x>>a[i].y;
    
    sort(a+1,a+n+1,cmp);
    
    fout<<setprecision(6)<<fixed<<solutie(1,n);
    
    return(0);
}