Cod sursa(job #2601041)

Utilizator smoc_georgemarianSmoc George-Marian smoc_georgemarian Data 13 aprilie 2020 17:25:20
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
typedef long long i64;

const int NMAX = 100005;
const i64 INF = 4e18;
vector< pair<i64,i64>> X,Y,V(NMAX);
int n;
i64 dist( pair<i64,i64>a, pair<i64,i64>b)
{
  return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
i64 det1( int st, int dr, vector< pair<i64,i64>> X, vector< pair<i64,i64>>Y);
i64 abs1( i64 a, i64 b)
{
   if(a>=b)
   return a-b ;
   return b-a;
}
void citire();
int main()
{citire();
 fout<<fixed<<setprecision(7)<< sqrt( det1( 0,n,  X, Y) ) ;
    return 0;
}
void citire()
{
  int i;
  int x,y;
  assert(fin>>n);
  for(i=0;i<n;i++)
    {
     assert(fin>>x>>y);
     assert( -1000000000<= x && x<=1000000000 );

     assert( -1000000000<= y && y<=1000000000 );
     X.push_back(    {x,y}   );

     Y.push_back({y,x});
    }
 sort(X.begin(),X. begin()+X.size() );

}

i64 det1( int st, int dr, vector< pair<i64,i64>> X, vector< pair<i64,i64>>Y)
{
  int mj=(dr+st)/2;
  if(st>=dr-1)
        return INF;
  if(st==dr-2)
    {
     if(Y[st]>Y[st+1])
            swap(Y[st],Y[st+1]);

     return dist (X[st],X[st+1]);
    }

  i64 ans1,ans2,minim;
  ans1= det1(st,mj,X,Y);

  ans1= det1(mj,dr,X,Y);
  minim=min(ans1,ans2);

  merge(Y.begin() + st, Y.begin() + mj, Y.begin() + mj, Y.begin() + dr, V.begin());
  copy(V.begin(), V.begin() + (dr - st), Y.begin() + st);
  int sz=0;
  for(int i=st;i<dr;i++)
    {
     if(   abs1( Y[i].second, X[mj].first   ) <=minim )
        {
         V[sz++]=Y[i];
        }

    }
   for(int i=0;i<sz;i++)
        for(int j=i+1;j<sz && j< i+8;j++)
            {
              minim= min(minim , dist( V[i], V[j]));
            }
return minim;
}