Cod sursa(job #2676900)

Utilizator AcuasPopescu Nicolae-Aurelian Acuas Data 25 noiembrie 2020 11:42:43
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.28 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <climits>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;

// Point represents a point on the plane xOy
struct Point {
    long long x, y;
    // Construct a comparator for sorting points in ascending order by X
    friend struct byX;
    struct byX {
        bool operator() (Point const &p1, Point const &p2) {
            return p1.x < p2.x;
        }
    };
    // Construct a comparator for sorting points in descending order by Y
    friend struct byY;
    struct byY {
        bool operator() (Point const &p1, Point const &p2) {
            return p1.y > p2.y;
        }
    };
};

// Function `read` opens the file `cmap.in` and it reads an integer `n` and
// `n` points. First, the function pushes into the vector `points` an auxiliary
// value which will not be used (We want to use indicies between 1 and n, not
// between 0 and n).
void read(long long &n, vector<Point> &points) {
    ifstream fin("cmap.in");
    fin >> n;
    Point aux;
    aux.x = LLONG_MAX;
    aux.y = LLONG_MAX;
    points.push_back(aux);
    for (int i = 1; i <= n; i++) {
        fin >> aux.x >> aux.y;
        points.push_back(aux);
    }
    fin.close();
}

// distance represents the euclidian distance between two points
double distance(const Point &A, const Point &B) {
    return sqrt(pow(A.x - B.x, 2) + pow(A.y - B.y, 2)); 
}

// minDistanceBetweenNPoints represents the minimum distance between ls - li
// points. This function is used when the number of points in a recursive call
// is less then 3
double minDistanceBetweenNPoints(int li, int ls, vector<Point> &points) {
    double minDist = LLONG_MAX;
    for (int i = li; i < ls; i++) {
        for (int j = i + 1; j <= ls; j++) {
            double auxDist = distance(points[i], points[j]);
            if (minDist > auxDist) {
                minDist = auxDist;
            }
        }
    }

    return minDist;
}

// divide is the principal function used in divide and conquer strategy
double divide(int li, int ls, vector<Point> &P, vector<Point> &Q) {
    if (ls - li < 3) {
        return minDistanceBetweenNPoints(li, ls, P);
    } 

    // Find the middle point in the sorted array
    int mid = (li + ls)/2;
    
    // Once the dividing line (P[mid]) is known, we step through Q
    // sequentially, placing each element in Ql and Qr, as appropiate
    vector<Point> Ql;
    Ql.push_back(Q[0]);
    vector<Point> Qr;
    Qr.push_back(Q[0]);
    for (int i = 1; i < Q.size(); i++) {
        if (Q[i].x <= P[mid].x) {
            Ql.push_back(Q[i]);
        } else {
            Qr.push_back(Q[i]);
        }
    }

    // Recursive calls
    double dl = divide(li, mid, P, Ql);
    double dr = divide(mid + 1, ls, P, Qr);
    double dmin = min(dl, dr);

    // When the recursive calls return, we scan through the Q list and
    // discard all the points whose x cooordinates are not within the 
    // strip. Then Q contains only points in the strip, and these points
    // are guaranteed to be sorted by their y coordinates
    vector<Point> strip;
    Point aux;
    aux.x = INT_MAX;
    aux.y = INT_MAX;
    strip.push_back(aux);
    for (int i = 1; i < Q.size(); i++) {
        if (abs(P[mid].x - Q[i].x) <= dmin) {
            strip.push_back(Q[i]);
        }
    }
    
    // Calculate the minimum distance of points in the strip
    for (int i = 1; i < strip.size() - 1; i++) {
        for (int j = i + 1; j < i + 8 && j < strip.size(); j++) {
            if (distance(strip[i], strip[j]) >= dmin) {
                break;
            } else if (distance(strip[i], strip[j]) < dmin) {
                dmin = distance(strip[i], strip[j]);
            }
        }
    }
    
    return dmin;
}

// Main function
int main() {
    // declare n and a vector of points
    long long n;
    vector<Point> P;
    // read n and the vector of points
    read(n, P);
    // make a copy of P
    vector<Point> Q = P;
    // sort P in ascending order by X coordinates
    sort(P.begin() + 1, P.end(), Point::byX());
    // sort Q in descending order by Y coordinates
    sort(Q.begin() + 1, Q.end(), Point::byY());
    // Calculate the minimum distance between the n points using 
    // divide and conquer
    ofstream fout("cmap.out");
    fout << fixed << setprecision(6) << divide(1, n, P, Q);
    fout.close();
    return 0;
}