Cod sursa(job #2073239)

Utilizator rares.opariucRares Opariuc rares.opariuc Data 22 noiembrie 2017 20:59:17
Problema Cele mai apropiate puncte din plan Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 2 kb
#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

void citire (int &n, vector <pair<int, int>> &PCT)
{
    ifstream f("cmap.in");
    f >> n;
    for(int i = 0; i < n; i++)
    {
        int x, y;
        f >> x >> y;
        PCT.push_back (make_pair (x, y));
    }
    f.close();
}

long long distanta (pair<int, int> A, pair<int, int> B)
{
    return (long long)(A.x - B.x) * (A.x - B.x) + (long long)(A.y - B.y) * (A.y - B.y);
}

bool cmp (pair<int, int> A, pair<int, int> B)
{
    return A.y < B.y;
}

long long di (int st, int dr, vector <pair<int, int>> &PCT, vector <pair<int, int>> &PCTsortateY)
{
    if(dr - st == 1)
        return INT_MAX;
    else if(dr - st == 2)
    {
        if (PCTsortateY[st].y > PCTsortateY[dr].y)
            swap(PCTsortateY[st], PCTsortateY[dr]);
        return distanta(PCT[st], PCT[dr]);
    }

    int m = (st + dr) / 2;
    long long dist = min (di(st, m, PCT, PCTsortateY), di(m + 1, dr, PCT, PCTsortateY));
    int delta = (int) (ceil(sqrt(dist)));

    vector<pair<int,int>> temp(dr - st);
    merge(PCTsortateY.begin() + st, PCTsortateY.begin() + m, PCTsortateY.begin() + m, PCTsortateY.begin() + dr, temp.begin(), cmp);
    copy(temp.begin(), temp.begin() + (dr - st), PCTsortateY.begin() + st);

    vector<pair<int,int>> temp2;
    for(unsigned i = st; i < dr; i++)
        if(abs(PCTsortateY[i].x - PCT[m].x) <= delta)
            temp2.push_back(PCTsortateY[i]);

    for(unsigned i = 0; i < temp2.size(); i++)
        for(unsigned j = i + 1; j < temp2.size() && temp2[j].y - temp2[i].y <= dist; j++)
            dist = min(dist, distanta (temp2[i], temp2[j]));

    return dist;
}

int main()
{
    int n;
    vector <pair<int, int>> PCT;

    citire(n, PCT);
    sort(PCT.begin(), PCT.end()); //sortare dupa x
    vector <pair<int, int>> PCTsortateY = PCT;

    ofstream g("cmap.out");
    g << fixed << setprecision(6) << sqrt(di(0, n, PCT, PCTsortateY));
    g.close();

    return 0;
}