Cod sursa(job #2677607)

Utilizator Botzki17Botocan Cristian-Alexandru Botzki17 Data 26 noiembrie 2020 21:14:54
Problema Cele mai apropiate puncte din plan Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.47 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <climits>

using namespace std;

typedef long long ll;

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


const ll INF  = LONG_LONG_MAX;
struct point
{
    ll x, y;
};
bool cmpx(point a, point b)
{
    return a.x <= b.x;
}

bool cmpy(point a, point b)
{
    return a.y <= b.y;
}



ll dist(point a, point b)
{
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

ll recur(vector<point> px, vector<point> py)
{
    if(px.size() <=3)
    {
        ll dmin = INF;
        for(int i=0; i < px.size()-1; i++){
            for(int j =i + 1; j < px.size(); j++)
                dmin = min(dmin, dist(px[i], px[j]));
        }

        return dmin;
    }
    int n = px.size();
    int median = n >>1;

    vector <point> drx;
    vector <point> dry;
    vector <point> stx;
    vector <point> sty;
    for(int i =0; i < px.size(); i++)
    {
        point p = px[i];
        if(i < median)
            {
                stx.push_back(p);
                sty.push_back(p);
            }
        else
            {
                drx.push_back(p);
                dry.push_back(p);
            }
    }
    ll xl = stx[stx.size() -1 ].x;
   /* for(int i =0; i < py.size(); i++)
    {
        point p = py[i];
        if(p.x <= xl)
            sty.push_back(p);
        else dry.push_back(p);
    }*/
    sort(dry.begin(), dry.end(), cmpy);
    ll dmin = min( recur(drx, dry), recur(stx, sty));

    vector <point> s;
    for(int i =0; i < py.size(); i++)
    {
        if(abs(py[i].x - xl)<=dmin)
            s.push_back(py[i]);
    }

    for(int i =0; i < s.size(); i++){
        point p = s[i];
        for(int j = i + 1; j < s.size() ; j++)
        {
            if(s[j].y - p.y > dmin)
                break;
            dmin = min(dmin, dist(p, s[j]));
        }
    }

    return dmin;

}

int main()
{
    int n, i;
    ll x, y;
    point a;
    fin>>n;
    vector <point> px;
    vector <point> py;
    for(i=1;i<=n;i++)
    {
        fin>>x>>y;
        a.x = x;
        a.y = y;
        px.push_back(a);
        py.push_back(a);
    }
    sort(px.begin(), px.end(), cmpx);
    sort(py.begin(), py.end(), cmpy);
    ll soll = recur(px,py);
    double sol = sqrt((double) soll);
    fout<<fixed<<showpoint;
    fout<<setprecision(17);
    fout<<sol<<"\n";


    return 0;
}