Cod sursa(job #2969230)

Utilizator albertaizicAizic Albert albertaizic Data 22 ianuarie 2023 19:02:56
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <algorithm>
#include <math.h>
#define NMAX 100000
#define INF 1000000000
using namespace std;
struct pct{
  int x,y;
};
pct v[NMAX];
pct p[NMAX];
int i,n,nr;

bool comp(const pct &a,const pct &b){
  if(a.x==b.x)
    return a.y<b.y;
  return a.x<b.x;
}
bool c(const pct &a,const pct &b){
  if(a.y==b.y)
    return a.x<b.x;
  return a.y<b.y;
}
double dist(const pct& a, const pct& b) {
  return sqrt((double)(a.x - b.x) * (a.x - b.x) + (double)(a.y - b.y) * (a.y - b.y));
}

double ver(double d){
  int j;
  sort(p,p+nr,c);
  for(i=0;i<nr-1;i++){
    j=i+1;
    while(j<nr && p[j].y-p[i].y<d){
      d=min(d,dist(p[i],p[j]));
      j++;
    }
  }
  return d;
}

double solve(int l,int r){
  if(r-l+1<=3){
    double mmin=INF;
    for(i=l+1;i<=r;i++){
      mmin=min(mmin,dist(v[l],v[i]));
    }
    return mmin;
  }else{
    double d;
    int m=(l+r)/2;
    d=min(solve(l,m),solve(m+1,r));
    nr=0;
    for(;l<=r;l++){
      if(abs(v[l].x-v[m].x)<d){
        p[nr++]=v[l];
      }
    }

    return min(d,ver(d));
  }
}


int main(){
    FILE *fin,*fout;
    fin=fopen("cmap.in","r");
    fout=fopen("cmap.out","w");

    fscanf(fin,"%d",&n);
    for(i=0;i<n;i++){
      fscanf(fin,"%d%d",&v[i].x,&v[i].y);
    }

    sort(v,v+n,comp);

    fprintf(fout,"%.6f",solve(0,n-1));



    fclose(fin);
    fclose(fout);
    return 0;
}