Cod sursa(job #2074281)

Utilizator stefanmereutaStefan Mereuta stefanmereuta Data 24 noiembrie 2017 13:01:24
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.14 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
#include <math.h>

using namespace std;

class Punct
{
public:
    int x, y;

    Punct()
    {
        x = y = 0;
    }

    Punct(int x, int y)
    {
        this->x = x;
        this->y = y;
    }

    bool operator<(Punct const &other) const
    {
        return x < other.x;
    }

    double dist(Punct const &other) const
    {
        //cout << "dist=sqrt(" << ((long long) x - other.x) * (x - other.x) + ((long long)y - other.y) * (y - other.y) << ")\n";
        return sqrt(((long long) x - other.x) * (x - other.x) + ((long long) y - other.y) * (y - other.y));
    }
};

bool CompY (Punct const &a, Punct const &b)
{
    return a.y < b.y;
}

vector<Punct> puncte, aux;

//left e inceputul, mid e mijloc + 1, right e sfarsitul + 1
//a si b sunt elementele cele mai apropiate
pair<Punct, Punct> DivImp(int left, int right)
{
    if (right - left < 4) {
        pair<Punct, Punct> closest = make_pair(puncte[left], puncte[right - 1]);

        for (int i = left; i < right; ++i) {
            for (int j = i + 1; j < right; ++j) {
                if (puncte[i].dist(puncte[j]) < closest.first.dist(closest.second)) {
                    closest = make_pair(puncte[i], puncte[j]);
                }
            }
        }

        return closest;
    } else {
        int mid = (left + right + 1) / 2;

        double dreapta = (puncte[mid - 1].x + puncte[mid].x) / 2;

        pair<Punct, Punct> closest = DivImp(left, mid), closest2 = DivImp(mid, right);
        if (closest.first.dist(closest.second) > closest2.first.dist(closest2.second)) {
            closest = closest2;
        }

        double d = closest.first.dist(closest.second);

        inplace_merge(puncte.begin() + left, puncte.begin() + mid, puncte.begin() + right, CompY);

        vector<Punct> banda;

        for (int i = left; i < right; ++i) {
            if (dreapta - d <= puncte[i].x && puncte[i].x <= dreapta + d) {
                banda.push_back(puncte[i]);
            }
        }

        for (int i = 0; i < banda.size(); ++i) {
            for (int j = i + 1; j < i + 8 && j < banda.size(); ++j) {
                if (banda[i].dist(banda[j]) < d) {
                    d = banda[i].dist(banda[j]);
                    closest = make_pair(banda[i], banda[j]);
                }
            }
        }

        //cout << "dist " << d << "\n";
        return closest;
    }
}

int main()
{
    fstream fin("cmap.in");
    fstream fout("cmap.out");

    int n;
    Punct aux;
    fin >> n;
    puncte.resize(n);

    for (int i = 0; i < n; ++i) {
        fin >> aux.x >> aux.y;
        puncte[i] = aux;
    }

    sort(puncte.begin(), puncte.end());

    pair<Punct, Punct> closest = DivImp(0, n);

    //cout << "(" << closest.first.x << "," << closest.first.y << "), (" << closest.second.x << "," << closest.second.y << ")\n";
    //cout << "distanta: " << closest.first.dist(closest.second) << "\n";
    fout << closest.first.dist(closest.second);

    fin.close();
    fout.close();

    return 0;
}