Pagini recente » Cod sursa (job #2409233) | Cod sursa (job #1923307) | Cod sursa (job #2218143) | Istoria paginii runda/oni_2016_cl10_ziua1/clasament | Cod sursa (job #2492164)
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
#include <fstream>
using namespace std;
struct punct{
long long int x,y;
int id;
};
vector <punct> P;
long long length(punct a,punct b){
long long rv;
rv=( 1LL*(a.x-b.x)*(a.x-b.x) + 1LL*(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;
}
bool cmpPY(punct a,punct b){
if(a.y!=b.y)
return a.y<b.y;
else
return a.x<b.x;
}
long long rec(int s,int d){
// double a,b;
// int mid=(d-s)/2;
// if(mid - s>2)
// a=rec(P,s,mid);
// else{
// if(mid - s==2)
// return min(length(P[s],P[mid-1]) , length(P[mid-1],P[mid]));
// else
// return length(P[s],P[mid]);
// }
// if (d-(mid + 1)>2)
// b=rec(P,mid + 1,d);
// else{
// if(d-(mid + 1)==2)
// return min(length(P[mid+1],P[d-1]) , length(P[d-1],P[d]));
// else
// return length(P[mid+1],P[d]);
// }
// double r=min(a,b);
if(d-s<2)
return INT_MAX;
if(d-s==2)
return length(P[d],P[s]);
int mid=(s+d)/2;
long long r=min(rec(s,mid),rec(mid,d));
//cout<<sqrt(r)<<endl;
if(d-s>2){
vector <punct> Y;
punct aux;
long long x;
for(int i=s;i<d;i++){
aux.x=P[mid].x;
aux.y=P[i].y;
x=length(P[i],aux);
if(x<r)
Y.push_back(P[i]);
}
sort(Y.begin(),Y.end(),cmpPY);
long long MIN=r;
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]);
//cout<<"test";
if(x<MIN)
MIN=x;
}
}
//cout<<sqrt(MIN)<<endl<<endl;
return MIN;
}
else
return r;
}
int main()
{
ifstream in("cmap.in");
ofstream out("cmap.out");
int n;
in>>n;
punct aux;
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 s=0,d=n-1;
long long r=rec(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)<<sqrt(r);
return 0;
}