Cod sursa(job #1803186)

Utilizator timicsIoana Tamas timics Data 11 noiembrie 2016 08:25:27
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include<bits/stdc++.h>
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
ll INF = 4e18;

//sorted by x, sorted by y, helper
vector <pll> x,y,v;

ll dist(pll a, pll b) {
  return (a.fs - b.fs) * (a.fs - b.fs) + (a.sc - b.sc) * (a.sc - b.sc);
}
 
//solve for points st, ..., dr-1
ll solve(int st, int dr) {
  if (st >= dr - 1) return INF;
  if (dr - st == 2) {
    if (y[st] > y[st + 1]) {
      swap(y[st], y[st + 1]);
    }
    return dist(y[st], y[st + 1]);
  }
  int mij = (st + dr) / 2;
  long long ret = min(solve(st, mij), solve(mij, dr));
  
  //sort by y using merge sort
  merge(y.begin() + st, y.begin() + mij, y.begin() + mij, y.begin() + dr, v.begin());
  copy(v.begin(), v.begin() + (dr - st), y.begin() + st);
  
  //find all points with x within ret of middle, sorted by y
  int nr = 0;
  for (int i=st; i<dr; ++i) {
    if (abs(y[i].sc - x[mij].fs) <= ret) {
      v[nr++] = y[i];
    }
  }
  
  //for each point look at at most 7 more points
  for (int i=0; i<nr; ++i) {
    for (int j=i+1; j<nr && j<=i+7; ++j) {
      ret = min(ret, dist(v[i], v[j]));
    }
  }
  return ret;
}
 
double closest_points(vector<pll> &a) {
  int N = a.size();
  x = a;
  v.resize(N); 
  sort(x.begin(), x.end());
  for(int i=0;i<N;++i) {
    y.pb(mp(x[i].sc, x[i].fs));
  }
  return sqrt(solve(0,N));
}
 
int main() {
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    int N;
    vector<pll> a;
    scanf("%d",&N);
    a.resize(N);
    for (int i = 0; i < N; ++ i) {
      scanf("%lld%lld",&a[i].fs,&a[i].sc);
    }
    printf("%.10lf\n",closest_points(a));
    return 0;
}