Cod sursa(job #1242986)

Utilizator teoionescuIonescu Teodor teoionescu Data 15 octombrie 2014 13:25:57
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.15 kb
#include<fstream>
#include<algorithm>
#include<queue>
#include<cmath>
#define abs(x) ((x>0)?(x):(-(x)))
#define min(a,b) ((a)<(b)?(a):(b))
#define x first
#define y second
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
typedef long long ll;
const int posmax=1<<8;
char buff[posmax]; int pos=posmax;
bool rable(char &c){return ( ('0'<=c && c<='9') || c=='-' );}
void refr(){if(pos>=posmax) in.read(buff,posmax),pos=0;}
void Read(ll &x){
    int sm=1;
    x=0,refr();
    while(!rable(buff[pos])) pos++,refr();
    while(rable(buff[pos])){
        if(buff[pos]=='-') sm=-sm;
        else x=x*10+int(buff[pos])-'0';
        pos++;
        refr();
    }
    x*=sm;
}
const int Nmax = 100001;
const ll INF = 0x3f3f3f3f3f3f3f3f;
pair<ll,ll> v[Nmax],temp[Nmax];
queue< pair<ll,ll> > q;
int N;
ll dist(const pair<ll,ll> &a,const pair<ll,ll> &b){
    return ( 1LL*(a.x-b.x)*(a.x-b.x) + 1LL*(a.y-b.y)*(a.y-b.y) );
}
ll solve(int st,int dr){
    if(st>=dr){
        return INF;
    }
    else{
        int mij=(st+dr)/2;
        ll midX=v[mij].x;
        ll da=solve(st,mij);
        ll db=solve(mij+1,dr);
        ll sol=min(da,db);
        ll nwsol=sol;
        int a=st,b=mij+1,k=0;
        while(a<=mij && b<=dr){
            if(v[a].y<v[b].y) temp[++k]=v[a++];
            else temp[++k]=v[b++];
        }
        while(a<=mij) temp[++k]=v[a++];
        while(b<=dr) temp[++k]=v[b++];
        for(int i=st;i<=dr;i++){
            v[i]=temp[i-st+1];
            if(abs(v[i].x-midX) <= sol){
                int size=q.size();
                for(int j=1;j<=size;j++){
                    pair<ll,ll> t=q.front();q.pop();
                    ll dd=dist(v[i],t);
                    nwsol=min(nwsol,dd);
                    q.push(t);
                }
                q.push(v[i]);
                if(q.size()>8) q.pop();
            }
        }
        while(!q.empty()) q.pop();
        return nwsol;
    }
}
int main(){
    in>>N;
    for(int i=1;i<=N;i++) Read(v[i].x),Read(v[i].y);
    sort(v+1,v+N+1);
    ll ans = solve(1,N);
    out.precision(6);
    out<<fixed<<sqrt(ans)<<'\n';
    return 0;
}