Cod sursa(job #2424664)

Utilizator ianiIani Biro iani Data 23 mai 2019 17:21:18
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

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

typedef pair<int,int> dublu;
vector<dublu> p;

bool cmp(dublu a,dublu b)
{
    if (a.first!=b.first)
        return a.first<b.first;
    return a.second<b.second;
}

long double dist(dublu a,dublu b)
{
    return sqrt(1LL*(a.first-b.first)*(a.first-b.first)+1LL*(a.second-b.second)*(a.second-b.second));
}

long double divide(int st,int dr)
{
    if (dr-st<=2)
    {
        long double v,mini=20000000;
        for (int i=st;i<=dr;i++)
        {
            v=dist(p[i],p[i+1]);
            if (v<mini)
                mini=v;
        }
        v=dist(p[st],p[dr]);
        if (v<mini)
            mini=v;
        return mini;
    }
    int mij=(st+dr)/2;
    ///TODO
    return min(divide(st, mij),divide(mij+1,dr));
}

int main()
{
    int n;
    fin>>n;
    for (int i=0;i<n;i++)
    {
        int x,y;
        fin>>x>>y;
        p.push_back(make_pair(x, y));
    }
    sort(p.begin(), p.end(), cmp);
    fout<<setprecision(6)<<fixed<<divide(0, n);
    return 0;
}