Pagini recente » Cod sursa (job #1855664) | Cod sursa (job #2954866) | Cod sursa (job #3198940) | Rating Zaharie Filip (Bismarck) | Cod sursa (job #486174)
Cod sursa(job #486174)
/*
* 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());
double sol=rez(0,punct.size(),punct,punct2);
sol=sqrt(sol);
g<<fixed<<setprecision(6)<<sol;
return 0;
}