// Herramientas para revisar el lema de la franja del par más cercano. Todo es fuerza bruta:
// estos programas comprueban afirmaciones de los apuntes con pocos puntos, y no sirven para
// muchos puntos porque cuestan Θ(n²).
#ifndef STRIP_H
#define STRIP_H

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <limits>
#include <vector>

struct Point {
    long long x;
    long long y;
    bool operator==(const Point&) const = default;
};

inline long long dist2(const Point& p, const Point& q) {
    long long dx = p.x - q.x;
    long long dy = p.y - q.y;
    return dx * dx + dy * dy;
}

inline long long brute_force(const std::vector<Point>& points) {
    long long best = std::numeric_limits<long long>::max();
    for (std::size_t i = 0; i < points.size(); i++) {
        for (std::size_t j = i + 1; j < points.size(); j++) {
            best = std::min(best, dist2(points[i], points[j]));
        }
    }
    return best;
}

struct StripPoint {
    Point point;
    bool from_left;
};

struct RootStep {
    long long line;                // ℓ: la x del punto en la posición n div 2
    long long left_best;           // δ² de la mitad izquierda
    long long right_best;          // δ² de la mitad derecha
    long long delta2;              // δ²: el menor de los dos
    std::vector<StripPoint> strip;  // los puntos con (x - ℓ)² < δ², ordenados por y
    long long max_gap;              // el mayor j - i entre puntos de la franja con distancia² < δ²
    long long best_in_strip;        // la menor distancia² entre esos pares; δ² si no hay ninguno
    bool all_crossing;              // ¿todos esos pares tienen un punto de cada mitad?
};

// El primer nivel de la división, calculado por fuerza bruta. `points` ya debe venir ordenado por x
// y el orden entre puntos de igual y en la franja es el que traiga la entrada: `points` puede
// barajarse antes para probar otros desempates.
inline RootStep analyze_root(const std::vector<Point>& points) {
    assert(points.size() >= 4);
    std::size_t mid = points.size() / 2;
    std::vector<Point> left(points.begin(), points.begin() + static_cast<long>(mid));
    std::vector<Point> right(points.begin() + static_cast<long>(mid), points.end());
    RootStep step{};
    step.line = points[mid].x;
    step.left_best = brute_force(left);
    step.right_best = brute_force(right);
    step.delta2 = std::min(step.left_best, step.right_best);
    for (std::size_t i = 0; i < points.size(); i++) {
        long long dx = points[i].x - step.line;
        if (dx * dx < step.delta2) {
            step.strip.push_back({points[i], i < mid});
        }
    }
    std::stable_sort(step.strip.begin(), step.strip.end(),
                     [](const StripPoint& p, const StripPoint& q) { return p.point.y < q.point.y; });
    step.best_in_strip = step.delta2;
    step.all_crossing = true;
    for (std::size_t i = 0; i < step.strip.size(); i++) {
        for (std::size_t j = i + 1; j < step.strip.size(); j++) {
            long long d = dist2(step.strip[i].point, step.strip[j].point);
            if (d < step.delta2) {
                step.max_gap = std::max(step.max_gap, static_cast<long long>(j - i));
                step.best_in_strip = std::min(step.best_in_strip, d);
                if (step.strip[i].from_left == step.strip[j].from_left) {
                    step.all_crossing = false;
                }
            }
        }
    }
    return step;
}

// Compara cada punto de la franja solo con sus `window` siguientes.
inline long long best_with_window(const RootStep& step, std::size_t window) {
    long long best = step.delta2;
    for (std::size_t i = 0; i < step.strip.size(); i++) {
        for (std::size_t j = i + 1; j < step.strip.size() && j <= i + window; j++) {
            best = std::min(best, dist2(step.strip[i].point, step.strip[j].point));
        }
    }
    return best;
}

inline void sort_by_x(std::vector<Point>& points) {
    std::stable_sort(points.begin(), points.end(), [](const Point& p, const Point& q) { return p.x < q.x; });
}

#endif