Cod sursa(job #2487980)

Utilizator stan_flaviusStan Flavius Stefan stan_flavius Data 5 noiembrie 2019 22:06:39
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.45 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#define nmax 100001

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

struct punct
{
    int x,y;
};

vector<punct>pct;
int n;

bool cmp_x(punct A,punct B)
{
    if(A.x==B.x) return A.y<B.y;
    return A.x<B.x;
}

bool cmp_y(punct A,punct B)
{
    return A.y<B.y;
}

double calc_dist(punct A,punct B)
{
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}

double search_dist_min(vector<punct>P,int left,int right)
{
    double mn=1e9;
    for(int i=left; i<right; i++)
        for(int j=i+1; j<=right; j++)
            {
                //fout<<P[i].x<<" "<<P[i].y<<" "<<P[j].x<<" "<<P[j].y<<" "<<calc_dist(P[i],P[j])<<"\n";
                if(calc_dist(P[i],P[j])<mn) mn=calc_dist(P[i],P[j]);
            }
    return mn;
}

double sol(vector<punct>P,int left,int right)
{
    if(right-left<=3)
        return search_dist_min(P,left,right);

    int mid=(right-left)/2;

    double dist_left=sol(P,left,mid);
    double dist_right=sol(P,mid+1,right-1);

    double dist_min=min(dist_left,dist_right);

    int val=P[mid].x;
    vector<punct>pct_closest;
    int ct=0;
    for(int i=left; i<=right; i++)
        if(abs(P[i].x-val)<dist_min)
            pct_closest.push_back(P[i]);
    sort(pct_closest.begin(),pct_closest.end(),cmp_y);

    double dist_min_2=1e9;
    if(pct_closest.size()>=8)
        {
            for(int i=0; i<=pct_closest.size()-7-1;  i++)
                for(int j=i+1; j<=i+7; j++)
                    if(calc_dist(pct_closest[i],pct_closest[j])<dist_min_2)
                        {
                            //fout<<"DA";
                            dist_min_2=calc_dist(pct_closest[i],pct_closest[j]);
                        }
        }
    else
        {
            for(int j=1; j<pct_closest.size(); j++)
                if(calc_dist(pct_closest[0],pct_closest[j])<dist_min_2)
                    {
                        //fout<<"DA";
                        dist_min_2=calc_dist(pct_closest[0],pct_closest[j]);
                    }
        }
    //fout<<dist_min<<" "<<dist_min_2<<"\n";*/
    return min(dist_min,dist_min_2);
}

int main()
{
    fin>>n;
    for(int i=0; i<n; i++)
        {
            punct p;
            fin>>p.x>>p.y;
            pct.push_back(p);
        }
    sort(pct.begin(),pct.end(),cmp_x);
    fout<<sol(pct,0,n-1);
    return 0;
}