Cod sursa(job #2088353)

Utilizator crazylamaRiclea Andrei crazylama Data 15 decembrie 2017 00:20:57
Problema Cele mai apropiate puncte din plan Scor 95
Compilator cpp Status done
Runda Arhiva educationala Marime 2.64 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

ifstream in("cmap.in");
ofstream out("cmap.out");

struct Point {
    int x, y;
};

int pointsCompareFunctionYAxis(Point p1, Point p2) {
    return p1.y < p2.y;
}

int pointsCompareFunctionXAxis(Point p1, Point p2) {
    return p1.x < p2.x;
}

int nrPoints;
vector<Point> points;

void read() {
    in >> nrPoints;
    Point point;
    for (int i = 0; i < nrPoints; ++i) {
        in >> point.x >> point.y;
        points.push_back(point);
    }
}

long long int euclidianDistance(Point p1, Point p2) {
    return 1LL * (p1.x - p2.x) * (p1.x - p2.x) + 1LL * (p1.y - p2.y) * (p1.y - p2.y);
}

void intersect(int left, int right, int pivot) {
    int i = left, j = pivot + 1;
    vector<Point> temp;
    while (i <= pivot && j <= right) {
        if (points[i].y < points[j].y)
            temp.push_back(points[i++]);
        else
            temp.push_back(points[j++]);
    }
    while (i <= pivot)
        temp.push_back(points[i++]);
    while (j <= right)
        temp.push_back(points[j++]);
    for (int k = left; k <= right; ++k)
        points[k] = temp[k - left];
}

long long int getMinDistance(int left, int right) {
    if (right - left == 1) {
        if (points[left].y > points[right].y)
            swap(points[left], points[right]);
        return euclidianDistance(points[left], points[right]);
    }
    if (right - left == 2) {
        sort(points.begin() + left, points.begin() + right + 1, pointsCompareFunctionYAxis);
        return min(euclidianDistance(points[left], points[left + 1]),
                    min(euclidianDistance(points[left], points[left + 2]),
                        euclidianDistance(points[left + 1], points[left + 2])));
    }
    int pivot = (right - left) / 2 + left;
    long long int minDistance = min(getMinDistance(left, pivot), getMinDistance(pivot + 1, right));
    intersect(left, right, pivot);
    int bandWidth = ceil(sqrt(minDistance));
    vector<Point> band;
    for (int i = left; i <= right; ++i)
        if (abs(points[i].x - points[pivot].x) <= bandWidth)
            band.push_back(points[i]);
    int bandLength = band.size();
    for (int i = 0; i < bandLength; ++i)
        for (int j = i + 1; j <= i + 7 && j < bandLength; ++j)
            minDistance = min(minDistance, euclidianDistance(band[i], band[j]));
    return minDistance;
}

int main()
{
    read();
    sort(points.begin(), points.end(), pointsCompareFunctionXAxis);
    out << fixed << setprecision(6) << sqrt(getMinDistance(0, nrPoints - 1)) << '\n';
    return 0;
}