Cod sursa(job #2969139)

Utilizator CReaper1116Shang Cheng Lin CReaper1116 Data 22 ianuarie 2023 16:58:56
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct point{
  int y,x;
}v[100000];
bool cmp(point a,point b){
  if(a.y == b.y)return a.x < b.x;
  return a.y < b.y;
}
bool cmp2(point a,point b){
  if(a.x == b.x)return a.y < b.y;
  return a.x < b.x;
}
double dist(point a,point b){
  return sqrt(abs(a.y - b.y)*abs(a.y - b.y) + abs(a.x - b.x)*abs(a.x - b.x));
}
point v1[100000],v2[100000];
double solve(int l,int r){
  if(l == r)return 2e9;
  int mij = (l + r)/2;
  double d = min(solve(l,mij),solve(mij + 1,r));
  //fout<<l<<' '<<r<<' '<<d<<'\n';
  int line = v[mij].y;
  int cnt1 = 0,cnt2 = 0;
  for(int i = l;i <= mij;i++)if(abs(v[i].y - line) <= d)v1[cnt1++] = {v[i].y,v[i].x};
  for(int i = mij + 1;i <= r;i++)if(abs(v[i].y - line) <= d)v2[cnt2++] = {v[i].y,v[i].x};
  sort(v1,v1 + cnt1,cmp2);
  sort(v2,v2 + cnt2,cmp2);
  int l2 = 0,r2 = -1;
  for(int i = 0;i < cnt1;i++){
    while(r2 != cnt2 - 1 && abs(v2[r2 + 1].x - v[i].x) <= d){
      r2++;
    };
    while(l2 != cnt2 && abs(v2[l2].x - v[i].x) > d){
      l2++;
    };
    for(int j = l2;j <= r2;j++){
      d = min(dist(v2[j],v1[i]),d);
      //fout<<dist(v2[j],v[i])<<' '<<v2[j].y<<' '<<v2[j].x<<' '<<v[i].y<<' '<<v[i].x<<'\n';
    }
  }
  //fout<<l<<' '<<r<<' '<<d<<'\n';
  return d;
}
int main(){
  fout<<fixed<<setprecision(6);
  int n,i;
  fin>>n;
  for(i = 0;i < n;i++){
    fin>>v[i].y>>v[i].x;
  }
  sort(v,v + n,cmp);
  /*for(i = 0;i < n;i++){
    fout<<v[i].y<<' '<<v[i].x<<'\n';;
  }*/
  fout<<solve(0,n - 1);
  return 0;
}