Cod sursa(job #2677595)

Utilizator Botzki17Botocan Cristian-Alexandru Botzki17 Data 26 noiembrie 2020 21:01:53
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.36 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

typedef long long ll;


ifstream fin("cmap.in");
ofstream fout("cmap.out");



const ll INF  = LONG_LONG_MAX;
struct point
{
   ll x, y;
};
bool cmpx(point a, point b)
{
  return a.x <= b.x;
}

bool cmpy(point a, point b)
{
  return a.y <= b.y;
}



ll dist(point a, point b)
{
  return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

ll recur(vector<point> px, vector<point> py)
{
   if(px.size() <=3)
   {
      ll dmin = INF;
      for(int i=0; i < px.size()-1; i++){
        for(int j =i + 1; j < px.size(); j++)
            dmin = min(dmin, dist(px[i], px[j]));
      }
      return dmin;
   }
   int n = px.size();
   ll median;
   if(n & 1)
      median = px[(n >>1)].x;
   else{
      int index = n >>1;
      median = (px[index -1].x + px[index].x)>>1;
   }
   vector <point> drx;
   vector <point> dry;
   vector <point> stx;
   vector <point> sty;
   for(int i =0; i < px.size(); i++)
   {
       point p = px[i];
       if(p.x <= median)
           stx.push_back(p);
       else drx.push_back(p);
       p = py[i];
       if(p.x <= median)
           sty.push_back(p);
       else dry.push_back(p);
   }
   //fout<<drx.size()<<" "<<stx.size()<<"\n";
   ll dmin = min( recur(drx, dry), recur(stx, sty));
   ll xl = stx[stx.size() -1 ].x;
   vector <point> s;
   for(int i =0; i < py.size(); i++)
   {
      if(abs(py[i].x - xl)<=dmin)
        s.push_back(py[i]);
   }
   for(int i =0; i < s.size(); i++){
    point p = s[i];
    for(int j = i + 1; j < s.size() ; j++)
    {
      if(s[j].y - p.y > dmin)
        break;
      dmin = min(dmin, dist(p, s[j]));
    }
   }
   return dmin;

}

int main()
{
    int n, i;
    ll x, y;
    point a;
    fin>>n;
    vector <point> px;
    vector <point> py;
    for(i=1;i<=n;i++)
    {
       fin>>x>>y;
       a.x = x;
       a.y = y;
       px.push_back(a);
       py.push_back(a);
    }
    sort(px.begin(), px.end(), cmpx);
    sort(py.begin(), py.end(), cmpy);
   // ll soll = recur(px, py);
   // fout<<"mamam";
    double sol = sqrt(recur(px, py));
   // fout<<"maimw";
   // double sol = sqrt((double) soll);
    fout<<fixed<<showpoint;
    fout<<setprecision(17);
    fout<<sol<<"\n";


    return 0;
}