Cod sursa(job #2070768)

Utilizator calin13Calin Nicolau calin13 Data 19 noiembrie 2017 21:47:12
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.94 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
#include <limits>
using namespace std;

typedef pair<long, long> Point;

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

double dist(const Point &a, const Point &b)
{
    long long x = a.first - b.first;
    long long 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; ++i) {
        for (int j = i + 1; j <= r; ++j) {
            double d = dist(v[i], v[j]);
            if (d < ret) {
                ret = d;
                p0 = v[i];
                p1 = v[j];
            }
        }
    }
    return ret;
}

double closestPairLine(vector<Point> &L, Point &p0, Point &p1)
{
    double ret = numeric_limits<double>::max();
    for (int i = 0; i < L.size(); ++i) {
        for (int j = i+1; j < i + 7; ++j) {
            double d = dist(L[i], L[j]);
            if (d < ret) {
                ret = d;
                p0 = L[i];
                p1 = L[j];
            }
        }
    }
    return ret;
}

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+1, r, rp0, rp1);
    double d = min(dlmin, drmin);
    if (dlmin < drmin) {
        p0 = lp0;
        p1 = lp1;
    } else {
        p0 = rp0;
        p1 = rp1;
    }

    vector<Point> L;
    int i = l;
    while (i < m && (double)abs(P[i].first - P[m].first) > d) {
        ++i;
    }
    int j = m+1;
    while (i < m && j <= r && abs(P[j].first-P[m].first) <= d) {
        if (P[i].second < P[j].second) {
            L.push_back(P[i++]);
        } else {
            L.push_back(P[j++]);
        }
    }
    while (j <= r && abs(P[j].first-P[m].first) <= d) {
        L.push_back(P[j++]);
    }
    Point mp0, mp1;
    double dmid = closestPairLine(L, mp0, mp1);
    if (dmid < d) {
        p0 = mp0;
        p1 = mp1;
        return dmid;
    }
    return d;
}

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

int main()
{
    ifstream f("cmap.in");
    int n;
    f >> n;
    vector<Point> v(n);
    for (int i = 0; i < n; ++i) {
        f >> v[i].first >> v[i].second;
    }
    f.close();

    ofstream g("cmap.out");
    Point p0, p1;
    g.precision(6);
    g << fixed << solve(v, p0, p1) << "\n" << p0 << "\n" << p1;
//    cout.precision(6);
//    Point b1, b2;
//    cout << fixed << bruteForce(v, 0, v.size()-1, b1, b2) << "\n" << b1 << "\n" << b2 << "\n";
    g.close();
}