Cod sursa(job #3233300)

Utilizator MirceaDonciuLicentaLicenta Mircea Donciu MirceaDonciuLicenta Data 2 iunie 2024 22:42:04
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.5 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>

using namespace std;

struct Point {
    int x, y;
};

// Comparators for sorting points
bool compareX(const Point &a, const Point &b) {
    return a.x < b.x;
}

bool compareY(const Point &a, const Point &b) {
    return a.y < b.y;
}

// Function to calculate the distance between two points
double dist(const Point &p1, const Point &p2) {
    return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}

// Function to find the distance between the closest points in a strip
double stripClosest(vector<Point> &strip, double d) {
    double minDist = d;
    sort(strip.begin(), strip.end(), compareY);  // Sort the strip according to the y coordinate

    for (size_t i = 0; i < strip.size(); ++i) {
        for (size_t j = i + 1; j < strip.size() && (strip[j].y - strip[i].y) < minDist; ++j) {
            minDist = min(minDist, dist(strip[i], strip[j]));
        }
    }
    return minDist;
}

// Recursive function to find the smallest distance
double closestUtil(vector<Point> &points, size_t left, size_t right) {
    if (right - left <= 3) {
        double minDist = numeric_limits<double>::infinity();
        for (size_t i = left; i < right; ++i) {
            for (size_t j = i + 1; j < right; ++j) {
                minDist = min(minDist, dist(points[i], points[j]));
            }
        }
        return minDist;
    }

    size_t mid = left + (right - left) / 2;
    Point midPoint = points[mid];

    double dl = closestUtil(points, left, mid);
    double dr = closestUtil(points, mid, right);

    double d = min(dl, dr);

    vector<Point> strip;
    for (size_t i = left; i < right; ++i) {
        if (abs(points[i].x - midPoint.x) < d) {
            strip.push_back(points[i]);
        }
    }

    return min(d, stripClosest(strip, d));
}

// Function to find the smallest distance
double closest(vector<Point> &points) {
    sort(points.begin(), points.end(), compareX);
    return closestUtil(points, 0, points.size());
}

int main() {
    ifstream infile("cmap.in");
    ofstream outfile("cmap.out");

    int n;
    infile >> n;
    vector<Point> points(n);

    for (int i = 0; i < n; ++i) {
        infile >> points[i].x >> points[i].y;
    }

    double result = closest(points);
    outfile.precision(6);
    outfile << fixed << result << endl;

    infile.close();
    outfile.close();

    return 0;
}