Cod sursa(job #2452213)

Utilizator ivan.tudorIvan Tudor ivan.tudor Data 29 august 2019 22:30:59
Problema Cele mai apropiate puncte din plan Scor 75
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.01 kb
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<fstream>
#include<iomanip>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int N=1e5+5;
struct points{
  int x,y;
};
bool cmpx(points a,points b){
  if(a.x==b.x)
    return a.y<b.y;
  return a.x<b.x;
}
bool cmpy(points a,points b){
  if(a.y==b.y)
    return a.x<b.x;
  return a.y<b.y;
}
double minn(double a,double b){
  if(a<b)
    return a;
  return b;
}
points Px[N];
points Py[N];
double dist(points a,points b){
  double distsq=(double)(a.x-b.x)*(a.x-b.x)+(double)(a.y-b.y)*(a.y-b.y);
  distsq=(double)sqrt(distsq);
  return distsq;
}
double abss(double x){
  if(x>=0)
    return x;
  return -x;
}
double FindMinDist(points px[],points py[],int n){
  double mindist;
  if(n<=3){
    mindist=dist(px[1],px[2]);
    for(int i=1;i<=n;i++){
      for(int j=i+1;j<=n;j++){
        mindist=minn(mindist,dist(px[i],px[j]));
      }
    }
    return mindist;
  }
  points pyl[n/2+2],pyr[n/2+2];
  int lsz=0,rsz=0;
  for(int i=1;i<=n;i++){
    if(py[i].x<=px[n/2].x){
      pyl[++lsz]=py[i];
    }
    else{
      pyr[++rsz]=py[i];
    }
  }
  double mindist1,mindist2;
  mindist1=FindMinDist(px,pyl,lsz);
  mindist2=FindMinDist(px+n/2,pyr,rsz);
  mindist=minn(mindist1,mindist2);
  int nrs=0;
  points strip[n+2];
  for(int i=1;i<=n;i++){
    if(abss(((double)px[n/2].x-py[i].x))<=mindist){
      strip[++nrs]=py[i];
    }
  }
  for(int i=1;i<=nrs;i++){
    int j=i+1;
    while(j<=nrs && strip[j].y-strip[i].y<=mindist){
      mindist=minn(mindist,dist(strip[j],strip[i]));
      j++;
    }
  }
  return mindist;
}
int main()
{
    int n;
    fin>>n;
    //scanf("%d",&n);
    for(int i=1;i<=n;i++){
      fin>>Px[i].x>>Px[i].y;
      //scanf("%d%d",&Px[i].x,&Px[i].y);
      Py[i]=Px[i];
    }
    sort(Px+1,Px+n+1,cmpx);
    sort(Py+1,Py+n+1,cmpy);
    //cout<<FindMinDist(Px,Py,n);
    fout<<setprecision(100)<<FindMinDist(Px,Py,n);
    return 0;
}