Cod sursa(job #1988180)

Utilizator MotoAMotoi Alexandru MotoA Data 2 iunie 2017 12:57:50
Problema Cele mai apropiate puncte din plan Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <climits>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct Punct{
 int x,y;
};
Punct coord[100001],Banda[100001];
bool compx(const Punct &A,const Punct &B){
 return A.x<B.x;
}
bool compy(const Punct &A,const Punct &B){
 return A.y<B.y;
}
long long sqr(long long a){
 return a*a;
}

long long dist2(Punct A, Punct B){
 return sqr(A.x-B.x)+sqr(A.y-B.y);
}

long long distmin3(int p,int u){
 long long dmin=LONG_LONG_MAX,d;
 for(int i=p;i<u;i++)
  for(int j=i+1;j<=u;j++)
     if((d=dist2(coord[i],coord[j]))<dmin)dmin=d;
 return dmin;
}
 void interclas(int p,int m, int u){
  int i=p,j=m+1,k=p;
  for(;i<=m && j<=u;k++){
   if(compy(coord[i],coord[j]))Banda[k]=coord[i++];
    else Banda[k]=coord[j++];
  }
  while(i<=m)Banda[k++]=coord[i++];
  while(j<=u)Banda[k++]=coord[j++];
 }

long long Divide(int p,int u){
 if(u-p+1<=3) {
  sort(coord+p,coord+1+u,compy);
  return distmin3(p,u);
 }
 int m=(p+u)/2;
 int x=coord[m].x;
 long long ds=Divide(p,m);
 long long dd=Divide(m,u);
 long long dmin=min(ds,dd);
 interclas(p,m,u);
 int k=0;
 for(int i=p;i<=u;i++){
  coord[i]=Banda[i];
  if(sqr(coord[i].x-x<dmin)){
   Banda[++k]=coord[i];
  }
 }
 for(int i=1;i<k;i++)
  for(int j=i+1;j<=k && sqr(Banda[j].y-Banda[i].y)<dmin;j++)
   if((ds=dist2(Banda[i],Banda[j]))<dmin)dmin=ds;

 return dmin;
}

int main(){
 int n;
 f>>n;
 for(int i=1;i<=n;i++)
   f>>coord[i].x>>coord[i].y;
  sort(coord+1,coord+n+1,compx);
  double d=sqrt(Divide(1,n));
  g<<fixed<<setprecision(6)<<d;

}