Pagini recente » Cod sursa (job #2976216) | Cod sursa (job #1808871) | Cod sursa (job #1577228) | Cod sursa (job #2266112) | Cod sursa (job #2275267)
// O(n^2)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
#define x first
#define y second
#define INF 10000.0
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
typedef pair<int,int> punct;
vector<punct> v,vnou;
int n;
bool cmpy(punct a, punct b){ return a.y > b.y; }
bool cmpx(punct a, punct b){ return a.x > b.x; }
inline float dist(punct a, punct b){ return (float)sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)); }
float divide(int st, int dr){
int m = (st+dr)/2;
int n = dr-st+1;
if(n == 1) return INF;
else if( n==2) return dist(v[st],v[dr]);
else {
float dmin = min(divide(st,m), divide(m,dr));
float mij = (float)(v[st].y + v[dr].y)/2;
vnou.clear();
for(int i = st; i<=dr; i++){
if(mij - dmin <= v[i].y || mij + dmin >= v[i].y ){
vnou.push_back(v[i]);
}
}
float dmin_banda = INF;
for(int j=0;j<vnou.size()-1;j++){
for(int k=j+1;k<vnou.size();k++){
dmin_banda = min(dmin_banda, dist(v[k],v[j]));
}
}
return min(dmin,dmin_banda);
}
}
int main(){
in >> n;
v.resize(n);
for(int i=0;i<n;i++)
in >> v[i].x >> v[i].y;
sort(v.begin(),v.end(),cmpy);
out << fixed << setprecision(10) << divide(0,n-1);
return 0;
}