Cod sursa(job #2617558)

Utilizator horia_mercanHoria Mercan horia_mercan Data 21 mai 2020 23:07:27
Problema Cele mai apropiate puncte din plan Scor 65
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.86 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 (vector< pair<long long int, long long int> >::iterator p=vec.begin() ; p!=vec.end(); p++ )
    {
        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() <= 3)
    {
        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()
{
    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;
}