Cod sursa(job #2486605)

Utilizator Bianca00Buzoi Bianca Bianca00 Data 3 noiembrie 2019 11:05:55
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;

ifstream f("cmap.in");
ofstream g("cmap.out");

struct punct
{
    int x;
    int y;
};

bool comparamX(punct a, punct b)
{
    return a.x<b.x;
}

bool comparamY(punct a, punct b)
{
    return a.y<b.y;
}

int distanta(punct a, punct b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

int min_dist(vector<punct>v, int st, int dr)
{
    int m,d1,d2,dist_min,d;
    if (dr-st==1)
        return distanta(v[st],v[dr]);
    if(dr-st==2)
    {
        int k=distanta(v[st],v[st+1]);
        int w=distanta(v[st],v[dr]);
        int ww=distanta(v[st+1],v[dr]);
        vector <int> mini;
        mini.push_back(k);
        mini.push_back(w);
        mini.push_back(ww);
        sort(mini.begin(),mini.end());
        return mini[0];
    }
    m=(st+dr)/2;
    d1=min_dist(v,st,m);
    d2=min_dist(v,m,dr);
    if(d1<d2)
        dist_min=d1;
    else
        dist_min=d2;
   // dist_min=min(d1,d2);
    int i, j;
    d=(int)ceil(sqrt(dist_min));
    vector<punct>B;
    for(i=st; i<=m-1; i++)
    {
        if (v[m].x-v[i].x<=d)
            B.push_back(v[i]);
    }

    for(i=m+1; i<=dr; i++)
    {
        if (v[i].x-v[m].x<=d)
            B.push_back(v[i]);
        else
            break;
    }
    sort(B.begin(),B.end(),comparamY);
    for(i=0; i<B.size(); i++)
    {
        for(j=i+1; j<=i+7 && j<B.size(); j++)
        {
            int d3=distanta(v[i],v[j]);
            if(dist_min>d3)
                dist_min=d3;

        }
    }
    return dist_min;


}

int main()
{
    vector <punct> A;
    int i, n;
    f>>n;
    for(i=1; i<=n; i++)
    {
        punct c;
        f>>c.x>>c.y;
        A.push_back(c);
    }
    sort(A.begin(),A.end(),comparamX);
    g <<fixed<<setprecision(6) <<sqrt(min_dist(A, 0, n-1));
    f.close();
    g.close();
}