Cod sursa(job #2603664)

Utilizator 1nsanityPopescu Ion 1nsanity Data 20 aprilie 2020 16:47:34
Problema Cele mai apropiate puncte din plan Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.88 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <limits>

using namespace std;

bool cmpX(pair<long long int, long long int> &a, pair<long long int, long long int> b)
{
    return a.first < b.first;
}
bool cmpY(pair<long long int, long long int> &a, pair<long long int, long long int> b)
{
    return a.second < b.second;
}

double dist(pair<long long int, long long int> &a, pair<long long int, long long int> &b)
{
    return sqrt(pow(a.first - b.first, 2) + pow(a.second - b.second, 2));
}

double nSquaredSol(vector<pair<long long int, long long int>> &coordonate)
{
    double minDist = numeric_limits<double>::max();
    for (long long int i = 0; i < coordonate.size(); i++)
    {
        for (long long int j = i + 1; j < coordonate.size(); j++)
        {
            double d = dist(coordonate[i], coordonate[j]);
            if (d != 0)
                minDist = min(minDist, d);
        }
    }
    return minDist;
}

double getMinDistFromStrip(vector<pair<long long int, long long int>> &strip, double d)
{
    for (long long int i = 0; i < strip.size(); i++)
    {
        for (long long int j = i + 1; j < strip.size() && strip[j].second - strip[i].second < d; j++)
        {
            d = min(d, dist(strip[i], strip[j]));
        }
    }
    return d;
}

void showVect(vector<pair<long long int, long long int>> &vec)
{
    for (pair<long long int, long long int> &p : vec)
    {
        cout << p.first << " " << p.second << "\n";
    }
    cout << "\n";
}

double solve(vector<pair<long long int, long long int>> &sortatX, vector<pair<long long int, long long int>> &sortatY)
{
    if (sortatX.size() <= 10)
    {
        return nSquaredSol(sortatX);
    }

    pair<long long int, long long int> midPoint = sortatX[sortatX.size() / 2];

    vector<pair<long long int, long long int>> sortatX_st;
    vector<pair<long long int, long long int>> sortatX_dr;

    vector<pair<long long int, long long int>> sortatY_st;
    vector<pair<long long int, long long int>> sortatY_dr;

    for (long long int i = 0; i < sortatY.size(); i++)
    {
        if (sortatX[i].first <= midPoint.first)
        {
            sortatX_st.push_back(sortatX[i]);
        }
        else
        {
            sortatX_dr.push_back(sortatX[i]);
        }
        if (sortatY[i].first <= midPoint.first)
        {
            sortatY_st.push_back(sortatY[i]);
        }
        else
        {
            sortatY_dr.push_back(sortatY[i]);
        }
    }

    double distSt = solve(sortatX_st, sortatY_st);
    double distDr = solve(sortatX_dr, sortatY_dr);

    double d = min(distSt, distDr);

    vector<pair<long long int, long long int>> strip;
    for (long long int i = 0; i < sortatY.size(); i++)
    {
        if (abs(sortatY[i].first - midPoint.first) < d)
        {
            strip.push_back(sortatY[i]);
        }
    }

    return min(d, getMinDistFromStrip(strip, d));
}

double nLognSol(vector<pair<long long int, long long int>> &coordonate)
{
    vector<pair<long long int, long long int>> sortatX(coordonate);
    vector<pair<long long int, long long int>> sortatY(coordonate);
    sort(sortatX.begin(), sortatX.end(), cmpX);
    sort(sortatY.begin(), sortatY.end(), cmpY);

    return solve(sortatX, sortatY);
}

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

int main()
{
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
    //fin.tie(NULL);

    long long int n;
    fin >> n;
    vector<pair<long long int, long long int>> coordonate(n);
    for (long long int i = 0; i < n; i++)
    {
        long long int x, y;
        fin >> x >> y;
        coordonate[i].first = x;
        coordonate[i].second = y;
    }

    double solutie = nLognSol(coordonate);
    fout << fixed;
    fout.precision(6);
    fout << solutie;

    return 0;
}