Cod sursa(job #2194368)

Utilizator PredaBossPreda Andrei PredaBoss Data 13 aprilie 2018 06:35:02
Problema Cele mai apropiate puncte din plan Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 2 kb
#include <bits/stdc++.h>
#define INF 1e15
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
vector<pair<int,int> >points;
vector<int>lines;
vector<int>::iterator low,up;
int n,x,y;
bool cmp(pair<int,int>a,pair<int,int>b)
{
    if(a.first==b.first)
        return a.second<b.second;
    return a.first<b.first;
}

long double divide(int pos1,int pos2)
{
    if(pos2-pos1>2)
    {
        long double s=min(divide(pos1,(pos1+pos2)/2),divide((pos1+pos2)/2+1,pos2));
        long long minpoint=points[(pos1+pos2)/2].first-s;
        long long maxpoint=points[(pos1+pos2)/2].first+s+1;
        low=lower_bound(lines.begin()+pos1,lines.begin()+pos2,minpoint);
        up=upper_bound(lines.begin()+pos1,lines.begin()+pos2,maxpoint)-1;
        int p1=low-lines.begin();
        int p2=up-lines.begin();
        for(int i=p1;i<=p2-1;i++)
            for(int j=i+1;j<=p2;j++)
                if(sqrt((points[i].first-points[j].first)*(points[i].first-points[j].first)+(points[i].second-points[j].second)*(points[i].second-points[j].second))<s)
                    s=sqrt((points[i].first-points[j].first)*(points[i].first-points[j].first)+(points[i].second-points[j].second)*(points[i].second-points[j].second));
        return s;
    }
    long double mn=INF;
    for(int i=pos1;i<=pos2-1;i++)
        for(int j=i+1;j<=pos2;j++)
        if(sqrt((points[i].first-points[j].first)*(points[i].first-points[j].first)+(points[i].second-points[j].second)*(points[i].second-points[j].second))<mn)
            mn=sqrt((points[i].first-points[j].first)*(points[i].first-points[j].first)+(points[i].second-points[j].second)*(points[i].second-points[j].second));
    return mn;
}
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>x>>y;
        points.push_back({x,y});
    }
    sort(points.begin(),points.end(),cmp);
    for(int i=0;i<n;i++)
        lines.push_back(points[i].first);
    fout<<setprecision(7);
    fout<<fixed;
    fout<<divide(0,n-1);
    return 0;
}