Cod sursa(job #1988167)

Utilizator MotoAMotoi Alexandru MotoA Data 2 iunie 2017 12:30:06
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 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;
}

long long Divide(int p,int u){
 if(u-p+1<=3) return distmin3(p,u);
 int m=(p+u)/2;
 long long ds=Divide(p,m);
 long long dd=Divide(m,u);
 long long dmin=min(ds,dd);

 int i=m,j=m,x=coord[m].x;
 int st=0,dr=0;
 while(st==0 && dr==0){
  i--;j++;
  if(st==0 && sqr(coord[i].x-x)>dmin)st=i+1;
  if(dr==0 && sqr(coord[j].x-x)>dmin)dr=j-1;
 }
 sort(coord+i,coord+j+1,compy);

 for(i=st;i<dr;i++)
  for(j=i+1;j<=dr && sqr(coord[j].y-coord[i].y)<dmin;j++)
   if((ds=dist2(coord[i],coord[j]))<dmin)dmin=ds;
 sort(coord+i,coord+j+1,compx);

 /*
 int k=0;
 for(int i=p;i<=u;i++)
 if(sqr(coord[i].x-coord[m].x<dmin)){Banda[++k]=coord[i];}
 sort(Banda+1,Banda+k+1,compy);
 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;
}