Cod sursa(job #2490134)

Utilizator lucianistratiIstrati Lucian lucianistrati Data 9 noiembrie 2019 19:57:11
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.91 kb

#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#include <map>
#define pb push_back
#define ll long long
using namespace std;

vector <pair<ll,ll> > v;
ll dist(pair <ll,ll> a,pair<ll,ll> b)
{
    int p1x=a.first;
    int p1y=a.second;
    int p2x=b.first;
    int p2y=b.second;
    return /*sqrt*/((double)((long long)((long long)p1x-p2x)*(p1x-p2x)+(long long)((long long)p1y-p2y)*(p1y-p2y)));
}
bool compare(pair <int,int> a,pair <int,int> b)
{
    if(a.first!=b.first)
    {
        return (a.first<b.first);
    }
    else
    {
        return (a.second<b.second);
    }
}
ll divideEtImpera(int st,int dr)
{
    int mij,minL,minR;
    ll d;
    if(dr-st==3)
    {
        ll first,nd,rd;
        first=dist(v[0],v[1]);
        nd=min(first,dist(v[1],v[2]));
        rd=min(nd,dist(v[0],v[2]));
        d=rd;
        return d;
    }
    if(dr-st==2 || dr-st==1)
    {
        d=dist(v[0],v[1]);
    }
    int i,j;
    mij=st+(dr-st)/2;
    d=min(divideEtImpera(st,mij),divideEtImpera(mij,dr));
    vector <pair<ll,ll> > new_v;
    for(i=st;i<dr;i++)
    {
        new_v.pb({v[i].first,v[i].second});
    }
    sort(new_v.begin(),new_v.end());
    for(i=0;i<new_v.size();i++)
    {
        for(j=i+1;j<new_v.size();j++)
        {
            if(j<i+8)
            {
                ll new_d;
                new_d=dist(new_v[i],new_v[j]);
                if(new_d<d)
                {
                    d=new_d;
                }
            }
        }
    }
}
int main()
{
    ifstream fin("cmap.in");
    ofstream fout("cmap.out");
    int n,i,j,a,b;
    double f;
    double min=999999999;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>a>>b;
        v.pb({a,b});
    }
    int dist_best=1e9;
    sort(v.begin(),v.end());
    dist_best=divideEtImpera(1,n);
    fout<<sqrt(dist_best);
    fin.close();
    fout.close();
    return 0;
}