Pagini recente » Cod sursa (job #2063091) | Cod sursa (job #1981384) | Cod sursa (job #2037158) | Cod sursa (job #1246691) | Cod sursa (job #2465372)
#include <fstream>
#include <algorithm>
#include <math.h>
#include <iomanip>
#define x first
#define y second
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n;
pair<long long, long long> v[100010], aux[100010], ch[100010];
long long Distanta(pair<long long, long long>a, pair<long long, long long>b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
void interclasare(int st, int mid, int dr){
int n=mid;
int m=dr;
int i=st;
int j=mid+1;
int k=st-1;
while(i<=n&&j<=m){
if(v[i].y<v[j].y){
k++;
aux[k]=v[i];
i++;
}else{
k++;
aux[k]=v[j];
j++;
}
}
for(;i<=n;i++){
k++;
aux[k]=v[i];
}
for(;j<=m;j++){
k++;
aux[k]=v[j];
}
for(i=st;i<=dr; i++){
v[i]=aux[i];
}
}
int modul(long long x,long long y){
if(x>y){
return x-y;
}
else{
return y-x;
}
}
long long dvd(long long st, long long dr){
long long s;
if(dr-st==1){
s=Distanta(v[st], v[dr]);
interclasare(st, st, dr);
return s;
}
if(dr-st==2){
s=min( Distanta(v[st], v[st+1]), Distanta(v[st+1], v[dr]) );
interclasare(st, st, st+1);
interclasare(st, st+1, dr);
return s;
}
long long mid=(st+dr)/2;
long long val1=dvd(st, mid);
long long val2=dvd(mid+1, dr);
interclasare(st, mid, dr);
s=min(val1, val2);
long long nr=0;
for(int i=st;i<=dr;i++){
if(modul(v[mid].x,v[mid].y) <= s){
nr++;
ch[nr]=v[i];
}
}
for(int i=1;i<=nr;i++){
for(int j=i+1; j<=nr && j<=i+7; j++){
s=min(s,Distanta(ch[i],ch[j]));
}
}
return s;
}
int main(){
fin>>n;
for(int i=1;i<=n;i++){
fin>>v[i].x>>v[i].y;
}
sort(v+1,v+n+1);
fout<<setprecision(6)<<fixed<<(double)sqrt( dvd(1,n) );
}