Cod sursa(job #3037891)

Utilizator Luca529Taschina Luca Luca529 Data 26 martie 2023 16:51:53
Problema Cele mai apropiate puncte din plan Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <vector>

using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct Pct{
long double i, j;
}x[100001];

bool C(Pct a, Pct b)
{if(a.i<b.i || (a.i==b.i && a.j<b.j))return 1;
 return 0;
}

long double Dist(int x1, int y1, int x2, int y2)
{long double a=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
 return a;
}

long double DQ(int st, int dr)
{if(dr-st+1<=3)
 {long double mini=2e9;
  for(int i=st;i<dr;i++)
  for(int j=i+1;j<=dr;j++)
  mini=min(mini, Dist(x[i].i, x[i].j, x[j].i, x[j].j));

  return mini;
 }
 else
 {int mij=(st+dr)/2;
  long double mini=min(DQ(st, mij), DQ(mij+1, dr));
  vector<Pct> y;

  for(int i=st;i<=dr;i++)
  if(abs(x[i].i-x[mij].i)<=mini)y.push_back(x[i]);

  for(int i=0;i<y.size()-1;i++)
  for(int j=i+1;j<y.size();j++)
  mini=min(mini, Dist(y[i].i, y[i].j, y[j].i, y[j].j));

  return mini;
 }
}

int main()
{   int n;
    fin>>n;
    for(int i=1;i<=n;i++)
    fin>>x[i].i>>x[i].j;

    sort(x+1, x+1+n, C);
    DQ(1, n);

    fout<<fixed<<setprecision(6)<<DQ(1, n);
    return 0;
}