Cod sursa(job #2073377)

Utilizator ursuadina98Ursu Adina ursuadina98 Data 23 noiembrie 2017 00:07:09
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.73 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct punct
{
    int x=0,y=0;
};
double distanta(punct a,punct b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmpX(const punct& a,const punct& b)
{
    return a.x<b.x;
}
bool cmpY(const punct& a,const punct& b)
{
    return a.y<b.y;
}

double dist_min(int st,int dr,vector<punct> &P,vector<punct> &Y)
{
    if((dr-st)==1)
    {
        return 2147483647;
        //m.p1.x=2147483647;
        //m.p1.y=2147483647;
       // m.p1.x=-2147483647;
        //m.p1.y=-2147483647;
    }
    else if((dr-st)==2)
    {
        if(Y[st].y>Y[st+1].y)
             swap(Y[st],Y[st+1]);
        return distanta(P[0],P[1]);
       // m.p1=P[0];
        //m.p2=P[1];
    }
    int d;
    double min_st,min_dr,min_p,min_p1;
   // min_p1.dis=1000000001;
    d=(st+dr)/2;
    min_st=dist_min(st,d,P,Y);
    min_dr=dist_min(d,dr,P,Y);
    if(min_st<min_dr)
        min_p=min_st;
    else
        min_p=min_dr;
    vector <punct> aux(dr-st);
    merge(Y.begin()+st,Y.begin()+d,Y.begin()+d,Y.begin()+dr,aux.begin(),cmpY);
    copy(aux.begin(),aux.begin()+(dr-st),Y.begin()+st);
    vector <punct> b;
    for (int i = st; i < dr; ++i)
    {
        if (abs(Y[i].x - P[d].x) <= min_p)
            b.push_back(Y[i]);
    }

    /// verificarea benzii
    double min_t = min_p;
    for (int i = 0; i<b.size(); ++i)
        for (int j = i + 1; j < b.size() && b[j].y - b[i].y <= min_p; ++j)
        {
            double c = distanta(b[i], b[j]);
            if (c < min_t)
            {
                min_t= c;
            }
        }

    return min_t;
    /*for(i=st; i<=dr; i++)
    {
        l=distanta(P[i],P[d]);
        if(l<=min_p.dis)
        {
            Y[k]=P[i];
            k++;
        }
    }
    //set <punct>::iterator i,j;
    sort(Y,Y+k,cmpY);
    for(i=0; i<k-1; i++)
    {
        for(j=i+1; j<k; j++)
            if(distanta(Y[i],Y[j])<=min_p.dis)
            {
                min_p1.dis=distanta(Y[i],Y[j]);
                min_p1.p1=Y[i];
                min_p1.p2=Y[j];
            }
    }
    if(min_p1.dis<min_p.dis)
    {
        min_p=min_p1;

    }
    return min_p;*/
}

int main()
{
    int i,n;
    punct p;
    double pct;

    f>>n;
    vector<punct> P(n);
    for(i=0; i<n; i++)
    {
        f>>P[i].x>>P[i].y;
    }
    sort(P.begin(),P.end(),cmpX);
    vector <punct> Y=P;
    pct=dist_min(0,P.size(),P,Y);
     g << fixed;
    g << setprecision(6) <<pct<<endl;
    /*<<pct.p1.x<<" "<<pct.p1.y<<endl<<pct.p2.x<<" "<<pct.p2.y;*/
    return 0;
}