Cod sursa(job #2491262)

Utilizator Bianca00Buzoi Bianca Bianca00 Data 12 noiembrie 2019 09:16:48
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.26 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, vector<punct> vv, 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;
    punct mij=v[m];
    vector <punct> Vstg;
    vector <punct> Vdr;
    int i;
    for(i=st;i<=dr;i++)
        if (vv[i-st].x<=mij.x)
            Vstg.push_back(vv[i]);
        else
            Vdr.push_back(vv[i]);
    d1=min_dist(v,Vstg,st,m);
    d2=min_dist(v,Vdr,m+1,dr);
    if(d1<d2)
        dist_min=d1;
    else
        dist_min=d2;
   // dist_min=min(d1,d2);
    int j;
    d=(int)ceil(sqrt(dist_min));
    vector<punct>B;
    for(i=st; i<=m-1; i++)
    {
        if (vv[m-st].x-vv[i-st].x<=d)
            B.push_back(vv[i]);
    }

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

        }
    }
    return dist_min;
}

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