Cod sursa(job #1623696)

Utilizator robertstrecheStreche Robert robertstreche Data 1 martie 2016 21:05:55
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <vector>
#include <cmath>
#include <fstream>
#include <iomanip>
#include <algorithm>

#define NMAX 100005
#define INF 1000000000000000000

using namespace std;

vector <pair <long long,long long > >v,u,S;

inline long long modul(long long x){
  if (x<0)return -x;
  return x;
}

inline long long min(long long a,long long b){
  if (a<=b)return a;
  return b;
}

inline long long dist(const pair <long long,long long >& a,const pair <long long,long long >& b){
      return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}

long long dei(int st,int dr){
   if (st==dr)return INF;
   if (st+1==dr){
        if (u[st]>u[dr])swap(u[st],u[dr]);
        return dist(u[st],u[dr]);
   }
   int m=(st+dr)/2;
   long long val1=dei(st,m);
   long long val2=dei(m+1,dr);
   long long sol=min(val1,val2);

    merge(u.begin()+st+1,u.begin()+m+1,u.begin()+m+1,u.begin()+dr+1,v.begin()+1);
    copy(v.begin()+1,v.begin()+(dr-st)+1,u.begin()+st+1);

   int nr=0;
   for (int i=st;i<=dr;i++)if (modul(u[i].second-v[m].first)<=sol)S[++nr]=u[i];

   for (int i=1;i<=nr;i++)
   for (int j=i+1;j<=nr && j-i<=7;j++){
      long long distance=dist(S[i],S[j]);
      sol=(sol<distance?sol:distance);
   }
   return sol;
}

int main()
{
    ifstream f("cmap.in");
    ofstream g("cmap.out");

    int n;
    f>>n;

    v.resize(n+1);u.resize(n+1);S.resize(n+1);
    for (int i=1;i<=n;i++)f>>v[i].first>>v[i].second;

    sort(v.begin(),v.end());
    for (int i=1;i<=n;i++)u[i]=make_pair(v[i].second,v[i].first);

    g<<fixed<<setprecision(6)<<(double)sqrt((long long) dei(1,n));

    fclose(stdin);
    fclose(stdout);
}