Cod sursa(job #3239781)

Utilizator andreic06Andrei Calota andreic06 Data 7 august 2024 16:00:47
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.53 kb
#include <bits/stdc++.h>

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

using int64 = long long;

const int N_MAX = 1e5;
const int64 myINF = (int64) 8e18 + 10;

static inline int64 myabs (int64 x) {
    if (x < 0) return -x;
    return x;
}
struct defPoint {
    int64 x, y;
    int64 dist2 (defPoint other) {
        int64 dx = x - other.x;
        int64 dy = y - other.y;
        int64 ret = dx * dx + dy * dy;

        return ret;
    }
} points[1 + N_MAX], aux[1 + N_MAX];

struct defAnswer {
    int64 dist2;
    defPoint A, B;
    bool operator < (defAnswer other) {return dist2 < other.dist2;}
};

bool sortY (defPoint A, defPoint B) {return A.y < B.y;}

const int CHECK = 10;
defAnswer divide (int left, int right) {
     /**for (int i = left; i <= right; i ++)
        cout << points[i].x << " " << points[i].y << "\n";
     cout << "\n\n";**/

     if (right - left <= 3) {
       defAnswer ret = {myINF, {0, 0}, {0, 0}};
       for (int i = left; i < right; i ++) {
          for (int j = i + 1; j <= right; j ++) {
             defAnswer aux = {points[i].dist2 (points[j]), points[i], points[j]};
             if (aux.dist2 < ret.dist2) ret = aux;
          }
       }
       sort (points + left, 1 + points + right, sortY);
       return ret;
     }
     else {
       int mid = left + (right - left) / 2;
       defAnswer leftAns = divide (left, mid);
       defAnswer rightAns = divide (mid + 1, right);
       int64 min_dist = min (leftAns.dist2, rightAns.dist2);
       /// left and right side already sorted by y
       int64 mid_x = -myINF;
       for (int i = left; i <= mid; i ++)
          mid_x = max (mid_x, points[i].x);

       int i = left, j = mid + 1, t = left;
       while (i <= mid && j <= right) {
          if (points[i].y <= points[j].y)
            aux[t ++] = points[i ++];
          else
            aux[t ++] = points[j ++];
       }
       while (i <= mid)
          aux[t ++] = points[i ++];
       while (j <= right)
          aux[t ++] = points[j ++];
       for (int t = left; t <= right; t ++)
          points[t] = aux[t];

       /**cout << "\n" << min_dist << "\n";
       for (int i = left; i <= right; i ++)
          cout << points[i].x << " " << points[i].y << "\n";**/

       vector<defPoint> best;
       for (int i = left; i <= right; i ++)
          if (myabs (mid_x - points[i].x) * myabs (mid_x - points[i].x) <= min_dist)
            best.push_back (points[i]);

       defAnswer mergeAns = {myINF, {0, 0}, {0, 0}};
       int T = best.size ();
       for (int i = 0; i < T; i ++) {
          for (int j = i + 1; j < min (T, i + CHECK); j ++)
             if (mergeAns.dist2 > best[i].dist2 (best[j]))
               mergeAns = {best[i].dist2 (best[j]), best[i], best[j]};
       }
       best.clear ();

       defAnswer ret = {myINF, {0, 0}, {0, 0}};
       if (leftAns < ret) ret = leftAns;
       if (rightAns < ret) ret = rightAns;
       if (mergeAns < ret) ret = mergeAns;
       return ret;
    }
}

bool sortX (defPoint A, defPoint B) {return A.x < B.x;}

int main()
{
   int n; in >> n;
   for (int i = 1; i <= n; i ++)
      in >> points[i].x >> points[i].y;
    sort (1 + points, 1 + points + n, sortX);
    defAnswer ret = divide (1, n);

    long double answer = ret.dist2;
    answer = sqrt (answer);
    out << fixed << setprecision (7) << answer;
    /**out << ret.A.x << " " << ret.A.y << "\n";
    out << ret.B.x << " " << ret.B.y << "\n";**/
    ///out << ret.dist2;

    return 0;
}