Cod sursa(job #1604402)

Utilizator c0rn1Goran Cornel c0rn1 Data 18 februarie 2016 11:21:41
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#define inf 0x3f3f3f3f

using namespace std;

int n;
struct Point {
   int x, y;
   Point(int xx, int yy){
      x = xx;
      y = yy;
   }
};
vector<Point> p;

void readData(){
   int x, y;
   scanf("%d\n", &n);
   for (int i = 1; i <= n; ++i){
      scanf("%d %d\n", &x, &y);
      p.push_back(Point(x, y));
   }
}

double dist(Point A, Point B){
   return sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));
}

double dist(Point A, int line){
   return abs(A.x - line);
}

bool cmpXY(Point A, Point B){
   return A.x < B.x || A.x == B.x && A.y < B.y;
}

bool cmpYX(Point A, Point B){
   return A.y < B.y || A.y == B.y && A.x < B.x;
}

double dei(int st, int dr){
   if (dr - st <= 3){
      double mini = inf;
      for (int i = st; i < dr-1; ++i)
         for (int j = i+1; j < dr; ++j)
            mini = min(mini, dist(p[i], p[j]));
      return mini;
   }
   int mijl = (dr+st)/2;
   double ps = dei(st, mijl);
   double pd = dei(mijl, dr);
   double pp = min(ps, pd);

   /// pp
   vector<Point> closeP;
   closeP.clear();
   for (int i = mijl-1; i >= 0 && dist(p[i], p[mijl].x) < pp; --i)
      closeP.push_back(p[i]);
   for (int i = mijl; i < dr && dist(p[i], p[mijl].x) < pp; ++i)
      closeP.push_back(p[i]);
   sort(closeP.begin(), closeP.end(), cmpYX);
   for (int i = 0; i < closeP.size(); ++i)
      for (int j = 1; j <= 7 && i+j < closeP.size(); ++j)
         pp = min(pp, dist(closeP[i], closeP[i+j]));

   return pp;
}

int main()
{
   freopen("cmap.in", "r", stdin);
   freopen("cmap.out", "w", stdout);
   readData();
   sort(p.begin(), p.end(), cmpXY);
   printf("%lf\n", dei(0, n));

   return 0;
}