Cod sursa(job #2194559)

Utilizator PredaBossPreda Andrei PredaBoss Data 13 aprilie 2018 18:53:08
Problema Cele mai apropiate puncte din plan Scor 75
Compilator cpp Status done
Runda Arhiva educationala Marime 2.09 kb
#include <bits/stdc++.h>
#define INF 1e15
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
vector<pair<long long,long long> >points;
vector<long long>lines;
vector<long long>::iterator low,up,md;
int n,x,y;
bool cmp(pair<long long,long long>a,pair<long long,long long>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();
        int mid=(pos1+pos2)/2;
        for(int i=p1;i<=mid;i++)
            for(int j=mid;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 && i!=j)
                    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;
}