Cod sursa(job #1803207)

Utilizator timicsIoana Tamas timics Data 11 noiembrie 2016 09:24:09
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fs first
#define sc second

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
vector<pair<pll,int> > v,x,y;
ll INF = 4e18;
int N;

ll dist(pll a, pll b) {
  return (a.fs - b.fs) * (a.fs - b.fs) + (a.sc - b.sc) * (a.sc - b.sc);
}

pair<ll,pii> solve(int st, int dr) {
  if (st >= dr - 1) return mp(INF,mp(0,0));
  if (dr - st == 2) {
    if (y[st] > y[st + 1]) {
      swap(y[st], y[st + 1]);
    }
    return mp(dist(x[st].fs, x[st + 1].fs),mp(x[st].sc, x[st+1].sc));
  }
  
  int mij = (st + dr) / 2;
  pair<ll,pii > ret = min(solve(st,mij),solve(mij,dr));
  
  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);
  
  int nr = 0; 
  for (int i=st; i<dr; ++i) {
    if (abs(y[i].fs.sc - x[mij].fs.fs) < ret.fs) {
      v[nr++] = y[i];
    }
  }
  for(int i=0;i<nr;++i) {
    for (int j=i+1; j<nr && j<=i+7; ++j) {
      ll d = dist(v[i].fs,v[j].fs);
      if(d < ret.fs) {
        ret = mp(d,mp(v[i].sc,v[j].sc));
      }
    }
  }
  return ret;
}

double closest_points() {
  int N = x.size();
  sort(x.begin(), x.end()); //sort polls by x
  v.resize(N);
  for(ll i=0;i<N;++i) {
    y.pb( mp(mp(x[i].fs.sc, x[i].fs.fs), x[i].sc));
  }
  return sqrt(solve(0,N).fs);
}

int main() {
  freopen("cmap.in","r",stdin);
  freopen("cmap.out","w",stdout);
  scanf("%d",&N);
  x.resize(N);
  for(int i=0;i<N;++i) {
    scanf("%lld%lld",&x[i].fs.fs,&x[i].fs.sc);
  }
  printf("%.10lf\n",closest_points());
}