Cod sursa(job #2073879)

Utilizator fr0yo1Adrian Sandru fr0yo1 Data 23 noiembrie 2017 19:54:50
Problema Cele mai apropiate puncte din plan Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 2.5 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<math.h>
#include <iomanip>
using namespace std;
//ifstream f("date.in");
ifstream f("cmap.in");
ofstream g("cmap.out");
int n;
long long cmp(const pair<long long,long long> &a,const pair<long long,long long> &b)
{
    return a.second<b.second;
}
long long dist(const pair<long long,long long> &a,const pair<long long,long long> &b)
{
    return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
void interclaseaza(vector< pair< long long,long long > > &y,int p1,int u1,int p2,int u2)
{vector< pair< long long,long long > > aux;
int auxp=p1;
    while(p1<=u1 && p2<=u2)
    {
        if(y[p1].second>y[p2].second)
        {
            aux.push_back(y[p2]);
            p2++;
        }
        else
        {
            aux.push_back(y[p1]);
            p1++;
        }
    }
    while(p1<=u1)
    {
        aux.push_back(y[p1]);
            p1++;
    }
    while(p2<=u2)
    {
        aux.push_back(y[p2]);
            p2++;
    }
    copy(aux.begin(),aux.end(),y.begin()+auxp);
}
long long div(vector< pair< long long,long long > > &x,vector< pair< long long,long long > > &y,long long st,long long dr)
{
    if((dr-st+1)<=4)
    {
        sort(y.begin()+st,y.begin()+dr+1,cmp);
        long long d=dist(y[0],y[1]);
        for(int i=st;i<dr;i++)
            for(int j=i+1;j<=dr;j++)
            if(dist(y[i],y[j])<d)
                d=dist(y[i],y[j]);
            return d;
    }
    else
    {long long d;
        int m=(st+dr)/2;
        long long d1=div(x,y,st,m);
        long long d2=div(x,y,m+1,dr);
        d=min(d1,d2);
        interclaseaza(y,st,m,m+1,dr);
        vector< pair< long long,long long > > ly;
        for(int i=st;i<=dr;i++)
        {
            if(y[i].first<=x[m].first+d && y[i].first>=x[m].first-d)
                ly.push_back(y[i]);
        }
        for(unsigned int i=0;i<ly.size()-1;i++)
            for(unsigned int j=i+1;j<j+7 && j<ly.size();j++)
            if(dist(ly[i],ly[j])<d)
            {
             d=dist(ly[i],ly[j]);
            }
        return d;
    }
}
int main()
{
    f>>n;
    vector< pair< long long,long long > > x;
    for(int i=0;i<n;i++)
        { long long a,b;
            f>>a>>b;
            x.push_back(make_pair(a,b));
        }
    sort(x.begin(),x.end());
    vector< pair< long long,long long > > y;
    y=x;
    g<< fixed << setprecision(10) <<sqrt(div(x,y,0,n-1));
    return 0;
}