Cod sursa(job #1567477)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 13 ianuarie 2016 12:41:18
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include<cstdio>
#include<cmath>
#include<set>
#include<algorithm>
#define ll long long
using namespace std;
struct cmpy
{
bool operator ()(const pair<ll,ll> & a1,const pair<ll,ll> & a2) const
{
    if(a1.second!=a2.second)
    return a1.second<a2.second;
    return a1.first<a2.first;
}
};
set<pair<ll,ll>,cmpy> st;
pair<ll, ll> ve[100005];
long long dist(pair<ll,ll> a,pair<ll,ll> b)
{
    return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
int main()
{
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
int n,i,j;
long long di,d2;
double ans;
set<pair<ll,ll>,cmpy> :: iterator it;
di=1000000000;
di=di*di*5;
d2=di;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lld%lld",&ve[i].first,&ve[i].second);
sort(ve+1,ve+n+1);
j=1;
for(i=1;i<=n;i++)
{
    while(ve[i].first>ve[j].first+d2)
    {
        st.erase(ve[j]);
    j++;
    }
    for(it=st.begin();it!=st.end();it++)
    if(dist(*it,ve[i])<di)
    {
        di=dist(*it,ve[i]);
        d2=sqrt(di);
    }
    st.insert(ve[i]);
}
ans=sqrt(di);
printf("%lf\n",ans);
    return 0;
}