Cod sursa(job #1167359)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 4 aprilie 2014 20:48:55
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.17 kb
#include <cmath>

#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<double, double> Point;

const double oo = 1e15;

vector<Point> Points;
double Answer;

class CompareY {
  public:
    bool operator()(const Point &a, const Point &b) const {
        if (a.y != b.y)
            return a.y < b.y;
        return a.x < b.x;
    }
};

inline double Distance(const Point &a, const Point &b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

double Solve(vector<Point> &points, const int from, const int to) {
    if (from + 1 >= to)
        return oo;
    if (from + 2 == to) {
        if (points[from].y > Points[to - 1].y)
            swap(points[from], points[to - 1]);
        return Distance(points[from], points[to]);
    }
    int middle = (from + to) / 2;
    double xAxis = points[middle].x;
    double minDistance = min(Solve(points, from, middle), Solve(points, middle, to));
    vector<Point> aux = vector<Point>(to - from);
    merge(points.begin() + from, points.begin() + middle, points.begin() + middle, points.begin() + to, aux.begin(), CompareY());
    for (int i = 0; i < to - from; ++i)
        points[from + i] = aux[i];
    vector<Point> current;
    for (int i = from; i < to; ++i)
        if (abs(xAxis - points[i].x) < minDistance)
            current.push_back(points[i]);
    for (int i = 0; i < int(current.size()); ++i)
        for (int j = i + 1; j < int(current.size()) && j - i < 8; ++j)
            minDistance = min(minDistance, Distance(current[i], current[j]));
    return minDistance;
}

void Solve() {
    sort(Points.begin(), Points.end());
    Answer = Solve(Points, 0, int(Points.size()));
}

void Read() {
    ifstream cin("cmap.in");
    int n;
    cin >> n;
    Points = vector<Point>(n);
    for (int i = 0; i < n; ++i)
        cin >> Points[i].x >> Points[i].y;
    cin.close();
}

void Print() {
    ofstream cout("cmap.out");
    cout << fixed << setprecision(8) << Answer << "\n";
    cout.close();
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}