Pagini recente » Cod sursa (job #458816) | Cod sursa (job #999236) | Cod sursa (job #2786778) | Cod sursa (job #1466587) | Cod sursa (job #2485522)
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
#include <fstream>
using namespace std;
struct punct{
int x,y;
int id;
};
double length(punct a,punct b){
double rv;
rv=sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
return rv;
}
bool cmpP(punct a,punct b){
if(a.x!=b.x)
return a.x<b.x;
else
return a.y<b.y;
}
int rec(vector<punct> P,int s,int d){
int a,b;
if(s==d)
return INT_MAX;
if(d/2 - s>1)
a=rec(P,s,d/2);
else{
return length(P[s],P[d/2]);
}
if(d - d/2 + 1>1)
b=rec(P,d/2 + 1,d);
else
return length(P[d/2 + 1],P[d]);
return min(a,b);
}
int main()
{
ifstream in("cmap.in");
ofstream out("cmap.out");
int n;
in>>n;
punct aux;
double x;
vector <punct> P;
vector <punct> Y;
for(int i=1;i<=n;i++){
in>>aux.x>>aux.y;
aux.id=i;
P.push_back(aux);
}
sort(P.begin(),P.end(),cmpP);
int midLine=P[n/2].x;
int s=0,d=n-1;
int r=rec(P,s,d);
for(int i=0;i<n;i++){
aux.x=midLine;
aux.y=P[i].y;
x=length(P[i],aux);
if(x<=r)
Y.push_back(P[i]);
}
double MIN=INT_MAX;
for(int i=0;i<Y.size()-1;i++){
for(int j=i+1;j<i+7 && j<Y.size();j++){
x=length(Y[i],Y[j]);
if(x<MIN)
MIN=x;
}
}
out<<setprecision(8)<<MIN;
return 0;
}