Cod sursa(job #486186)

Utilizator S7012MYPetru Trimbitas S7012MY Data 20 septembrie 2010 18:30:39
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
/*
 * File:   main.cpp
 * Author: petru
 *
 * Created on 2010-09-20
 */


#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iostream>
#define LL long long
#define deb(n) fprintf(stderr,"%d ",(n));
#define DN 100005
#define x first
#define y second
#define MULT 4e18
using namespace std;

typedef pair<LL,LL> PER;
int n;
vector <PER> punct,punct2,v(DN);

LL dist(const PER &a,const PER &b) {
    return (a.x - b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

double rez(int st,int dr,vector<PER> &a,vector<PER> &b){
    if(st>=dr-1) return MULT;//oprirea
    else if(dr-st==2) {//mai raman 2 puncte
        if(b[st]>b[st+1]) swap(b[st],b[st+1]);
        return dist(a[st],a[st+1]);
    }
    int mij=(st+dr)/2,i,cont=0;
    LL r=min(rez(st,mij,a,b),rez(mij,dr,a,b));
    merge(b.begin()+st,b.begin()+mij,b.begin()+mij,b.begin()+dr,v.begin());//combina 2 vectori sortati
    copy(v.begin(),v.begin()+(dr-st),b.begin()+st);
    for (i=st;i<dr;++i) if (abs(b[i].y-a[mij].x)<=r)
        v[cont++]=b[i];
    for (i=0;i<cont-1;++i)
        for (int j=i+1;j<cont&&j-i<8;++j)
            r=min(r,dist(v[i],v[j]));
    return r;

}

int main()
{
	int i;
	ifstream f("cmap.in");
	ofstream g("cmap.out");
	f>>n;
	punct.resize(n);
	punct2.resize(n);
	for(i=0; i<n; ++i) {
	    f>>punct[i].x>>punct[i].y;
	    punct2[i].y=punct[i].x;
	    punct2[i].x=punct[i].y;
	}
	sort(punct.begin(),punct.end());
	g<<fixed<<setprecision(6)<<sqrt(rez(0,punct.size(),punct,punct2));
	g.close();
	return 0;
}