Cod sursa(job #2601070)

Utilizator random.temaRandom Tema random.tema Data 13 aprilie 2020 18:12:03
Problema Cele mai apropiate puncte din plan Scor 75
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include<stdio.h>
#include<vector>
#include<fstream>
#include<cmath>

using namespace std;

typedef pair<int,int> point;

int64_t dist(point p1,point p2)
{
  return 1LL*(p1.first-p2.first)*(p1.first-p2.first)+1LL*(p1.second-p2.second)*(p1.second-p2.second);
}
void merge(vector<point> &v,vector<point> &aux,int left,int right,int m)
{
  int a=left,b=m+1,k=0;
  while(a<=m && b<=right)
    if(v[a].second<v[b].second)
      aux[k++]=v[a++];
    else
      aux[k++]=v[b++];
  while(a<=m) aux[k++]=v[a++];
  while(b<=right) aux[k++]=v[b++];
  for(int i=0;i<k;++i) v[left+i]=aux[i];
}
int64_t solve(vector<point> &v,vector<point> &aux,int left,int right)
{
  if(right-left<2)
    if(left==right) return 1e18;
    else
    {
      merge(v,aux,left,right,left);
      return dist(v[left],v[right]);
    }
  int m=(left+right)/2;
  int64_t sol=min(solve(v,aux,left,m),solve(v,aux,m+1,right));
  merge(v,aux,left,right,m);
  for(int i=left;i<=right;++i)
    for(int j=i-1;j>=left && i-j<8;--j)
      sol=min(sol,dist(v[i],v[j]));
  return sol;
}

int main()
{
  int n,i,j,x,s=0;
  vector<point> v;
  vector<point> aux;
  ifstream file;
  file.open("cmap.in");
  file>>n;
  v.resize(n);
  aux.resize(n);
  for(i=0;i<n;i++)
  {
    file>>x>>s;
    v[i]=make_pair(x,s);
  }
  file.close();
  FILE *out=fopen("cmap.out","w");
  fprintf(out, "%10f\n", sqrt((double)solve(v,aux,0,n-1)));
}