Cod sursa(job #2065240)

Utilizator calin13Calin Nicolau calin13 Data 13 noiembrie 2017 16:59:40
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.45 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
#include <limits>
using namespace std;

typedef pair<int, int> Point;

ostream& operator<<(ostream &os, const Point &p)
{
    os << p.first << " " << p.second;
    return os;
}

double dist(const Point &a, const Point &b)
{
    int x = a.first - b.first;
    int y = a.second - b.second;
    return sqrt(x*x + y*y);
}

double bruteForce(vector<Point> &v, int l, int r, Point &p0, Point &p1)
{
    double ret = numeric_limits<double>::max();
    for (int i = l; i < r-1; ++i) {
        for (int j = i + 1; j < r; ++j) {
            if (dist(v[i], v[j]) < ret) {
                ret = dist(v[i], v[j]);
                p0 = v[i];
                p1 = v[j];
            }
        }
    }
    return ret;
}

double closestPairLine(vector<Point> &L, double d, Point &p0, Point &p1)
{
    sort(
         L.begin(), L.end(),
         [](const Point &a, const Point &b) -> bool {
            return a.second < b.second;
         }
         );
    for (int i = 0; i < 6; ++i) {
        for (int j = i+1; j < 7; ++j) {
            if (dist(L[i], L[j]) < d) {
                d = dist(L[i], L[j]);
                p0 = L[i];
                p1 = L[j];
            }
        }
    }
    return d;
}

double closestPair(vector<Point> &P, int l, int r, Point &p0, Point &p1)
{
    if (r - l <= 3) {
        return bruteForce(P, l, r, p0, p1);
    }
    int m = l + (r-l)/2;
    Point lp0, lp1, rp0, rp1;
    double dlmin = closestPair(P, l, m, lp0, lp1);
    double drmin = closestPair(P, m, r, rp0, rp1);
    double d = min(dlmin, drmin);
    if (dlmin < drmin) {
        p0 = lp0;
        p1 = lp1;
    } else {
        p0 = rp0;
        p1 = rp1;
    }

    vector<Point> L;
    for (int i = l; i <= r; ++i) {
        if (abs(P[i].first - P[m].first) < d) {
            L.push_back(P[i]);
        }
    }
    return min(d, closestPairLine(L, d, p0, p1));
}

double cp(vector<Point> &p, Point &p0, Point &p1)
{
    sort(p.begin(), p.end());
    return closestPair(p, 0, p.size(), p0, p1);
}

int main()
{
    ifstream f("cmap.in");
    ofstream g("cmap.out");
    int n;
    f >> n;
    vector<Point> v(n);
    for (int i = 0; i < n; ++i) {
        f >> v[i].first >> v[i].second;
    }
    f.close();
    Point p0, p1;
    g.precision(6);
    g << fixed << cp(v, p0, p1);// << "\n" << p0 << "\n" << p1;
    g.close();
}