Cod sursa(job #2072069)

Utilizator lucianzr1Boaca Lucian lucianzr1 Data 21 noiembrie 2017 12:55:43
Problema Cele mai apropiate puncte din plan Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 4.81 kb
#include <iostream>
#include <vector>
#include <cmath>
#include <cfloat>
#include <sstream>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <unordered_map>

using namespace std;

struct Point {
    int x;
    int y;

    Point() = default;

    Point(int x, int y) : x(x), y(y) {}

    double distance(Point* p) {
        return sqrt(
                (this->x - p->x) * (this->x - p->x) +
                (this->y - p->y) * (this->y - p->y))
                ;
    }

    string toString() {
        stringstream ss;
        ss << "(x: "<<x<<", y: "<<y<<")";
        return ss.str();
    }
};

struct Pair {
    Point* p1;
    Point* p2;

    Pair(Point *p1, Point *p2) : p1(p1), p2(p2) {}

    Pair() : p1(nullptr), p2(nullptr) {}

    double distance() {
        return p1->distance(p2);
    }
};

double naive(const vector<Point*> &points, Pair & pair) {
    if (points.empty()) return DBL_MIN;
    if (points.size() == 1) return DBL_MAX;

    pair.p1 = points[0];
    pair.p2 = points[1];

    for (int i = 0; i < points.size() - 1; i++) {
        for (int j = i + 1; j < points.size(); j++) {
            if (points[i]->distance(points[j]) < pair.distance()) {
                pair.p1 = points[i];
                pair.p2 = points[j];
            }
        }
    }
    return pair.distance();
}

vector<Point*> read(istream &fin) {
    vector<Point*> points;

    int n;
    fin>>n;
    while (n) {
        int x, y;
        fin>>x>>y;
        points.push_back(new Point(x, y));
        n--;
    }

    return points;
}

//vector<Point*> read() {
//    vector<Point*> points;
//    points.push_back(new Point(1, 5));
//    points.push_back(new Point(6, 3));
//    points.push_back(new Point(2, 9));
//    points.push_back(new Point(1, 7));
//    points.push_back(new Point(7, 9));
//    points.push_back(new Point(6, 1));
//    points.push_back(new Point(10, 12));
//    points.push_back(new Point(0, 5));
//    points.push_back(new Point(-1, -4));
//    points.push_back(new Point(0, 0));
//    return points;
//}

double minStripDistance(vector<Point*> strip, double dist, Pair & pair) {
    double min = dist;

    for (int i = 0; i < strip.size(); i++) {
        for (int j = i +1 ; j < strip.size() && (strip[j]->y - strip[i]->y) < min; j++) {
            if (strip[i]->distance(strip[j]) < min) {
                min = strip[i]->distance(strip[j]);
                pair.p1 = strip[i];
                pair.p2 = strip[j];
            }
        }
    }

    return min;
}

// Divide and Conquer utility function
// px and py are vectors of points sorted by the x and y axes
// the pair argument is used to not only get the distance, but also the points from the algorithm
double compute(vector<Point*> px, vector<Point*> py, Pair & pair) {

    // base case
    if (px.size() <= 3) return naive(px, pair);

    // divide step
    Point* midPoint = px[px.size() / 2];

    unordered_map<Point*, int> mapSides;

    vector<Point*> pxL;
    vector<Point*> pxR;
    int side = -1;
    for (auto p : px) {
        if (p->x < midPoint->x) pxL.push_back(p);
        else if (p->x == midPoint->x) {
            if(side == -1) {
                pxL.push_back(p);
                mapSides[p] = -1;
            }
            else {
                pxR.push_back(p);
                mapSides[p] = 1;
            }
            side *= -1;
        }
        else pxR.push_back(p);
    }

    vector<Point*> pyL;
    vector<Point*> pyR;
    for (auto p : py) {
        if (p->x < midPoint->x) pyL.push_back(p);
        else if (p->x == midPoint->x) {
            if (mapSides[p] == -1) pyL.push_back(p);
            else pyR.push_back(p);
        }
        else pyR.push_back(p);
    }

    Pair pairL, pairR;
    double distL = compute(pxL, pyL, pairL);
    double distR = compute(pxR, pyR, pairR);

    // Conquer step
    double d;
    if (distL < distR) {
        d = distL; pair.p1 = pairL.p1; pair.p2 = pairL.p2;
    } else {
        d = distR; pair.p1 = pairR.p1; pair.p2 = pairR.p2;
    }

    vector<Point*> strip;
    for (auto p : py) {
        if (abs(p->x - midPoint->x) <= d) {
            strip.push_back(p);
        }
    }

    return min(d, minStripDistance(strip, d, pair));
}

double closest(vector<Point*> points, Pair& pair) {
    vector<Point*> px, py;
    for (auto p : points){
        px.push_back(p);
        py.push_back(p);
    }

    sort(px.begin(), px.end(), [](Point* p1, Point* p2) -> bool { return p1->x < p2->x; });
    sort(py.begin(), py.end(), [](Point* p1, Point* p2) -> bool { return p1->y < p2->y; });

    return compute(px, py, pair);
}

int main() {

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

    vector<Point*> pts = read(fin);

    Pair pair(nullptr, nullptr);

    double d = closest(pts, pair);

    fout<<setprecision(6)<<fixed<<d<<endl;

//    for (auto p : pts) {
//        delete p;
//    }

    fin.close();
    fout.close();
    return 0;
}