Cod sursa(job #1385844)

Utilizator PaueyPaula Nicoleta Gradu Pauey Data 12 martie 2015 14:43:57
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#include <cmath>
 
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
 
const int MAXN = 100005;
const long long inf = 4e18;
 
struct point {
   long long x, y;
};
 
int N;
point Px[MAXN];
point Py[MAXN];
vector<point> S;
 
bool cmp1(point a, point b) {
   if(a.x == b.x)
      return a.y < b.y;
   return a.x < b.x;
}
 
bool cmp2(point a, point b) {
   if(a.y == b.y)
      return a.x < b.x;
   return a.y < b.y;
}
 
long long dist(point a, point b) {
   return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
 
long long split(int st, int dr, long long d) {
   S.clear();
   int med = (st + dr) / 2;
   long long xm = Px[med].x;
   long long dmin = d;
   for(int i = 1; i <= N; ++i) {
      if(Py[i].x >= xm - d && Py[i].x <= xm + d) {
         S.push_back(Py[i]);
      }        
   }
   for(int i = 0; i < S.size() - 1; ++i) {
      for(int j = 1; j <= 7 && i + j < S.size(); ++j) {
         long long dc = dist(S[i], S[i + j]);
         if(dc < dmin)
            dmin = dc;
      }
   }
   return dmin;
}
 
long long solve(int st, int dr) {
   //cout << st << ' ' << dr << '\n';
   if(dr - st == 2) {
      return min(min(dist(Px[st], Px[st + 1]), dist(Px[st], Px[dr])), dist(Px[st + 1], Px[dr]));
   }
   if(dr - st == 1) {
      return dist(Px[st], Px[dr]);
   }
   long long d1 = solve(st, (st + dr) / 2);
   long long d2 = solve((st + dr) / 2 + 1, dr);
   //if(!d1 || !d2)
      //cout << st << ' ' << dr << ' ' << d1 << ' ' << d2 <<'\n';
   long long d3 = split(st, dr, min(d1, d2));
   return d3;
}
 
int main()
{
    ifstream cin("cmap.in");
    ofstream cout("cmap.out");
    cin >> N;
    for(int i = 1; i <= N; ++ i) {
      cin >> Px[i].x >> Px[i].y;
      Py[i] = Px[i];
    }
    sort(Px + 1, Px + N + 1, cmp1);
    sort(Py + 1, Py + N + 1, cmp2);
    cout << fixed << setprecision(6) << sqrt(1.0 * solve(1, N)) << '\n';
    return 0;
}