Cod sursa(job #2647580)

Utilizator victorzarzuZarzu Victor victorzarzu Data 5 septembrie 2020 12:31:26
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>

#define oo 0x3f3f3f3f
#define point pair<long long, long long> 
#define x first
#define y second

using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");

int n;
long long a, b, best = oo;
vector<point> p;
set<point> s;

long long dist(point p1, point p2)
{
  return (p1.y - p2.x) * (p1.y - p2.x) + (p1.x - p2.y) * (p1.x - p2.y);
}

void Solve()
{
  int pos = 0;
  s.insert(make_pair(p[0].y, p[0].x));
  for(int i = 1;i < n;++i)
  {
    while(pos < i && (p[pos].x - p[i].x) * (p[pos].x - p[i].x) > best)
    {
      s.erase(make_pair(p[pos].y, p[pos].x));
      ++pos;
    }

    set<point>::iterator it;
    it = lower_bound(s.begin(), s.end(), make_pair(p[i].y - best, p[i].x - best));
    int nr = 1;

    while((it != s.end()) && (nr <= 7))
    {
      best = min(best, dist((*it), p[i]));
      ++it;
      ++nr;
    }

    s.insert(make_pair(p[i].y, p[i].x));
  }
  g<<setprecision(6)<<fixed<<sqrt(best);
}

void Read()
{
  f>>n;
  for(int i = 1;i <= n;++i)
    {
      f>>a>>b; 
      p.push_back(make_pair(a, b));
    }
  sort(p.begin(), p.end());
}

int main()
{
  Read();
  Solve();
  return 1;
}