Pagini recente » Cod sursa (job #1074543) | Cod sursa (job #1085019) | Cod sursa (job #883345) | Cod sursa (job #1765089) | Cod sursa (job #2969232)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#define inl long long
#define MAXN 100005
using namespace std;
FILE *fin,*fout;
struct XY{
inl x,y;
};
XY poit[MAXN];
XY sir[MAXN];
inl dist=1e18;
inl Read(){
char a;
inl x,s;
a=fgetc(fin);
while(a!='-' && !isdigit(a)){
a=fgetc(fin);
}
if(a=='-'){
a=fgetc(fin);
s=-1;
}else{
s=1;
}
x=0;
while(isdigit(a)){
x=x*10+a-'0';
a=fgetc(fin);
}
return x*s;
}
bool cmp(XY a,XY b){
if(a.x==b.x){
return a.y<b.y;
}
return a.x<b.x;
}
bool ctr(XY a,XY b){
if(a.y==b.y){
return a.x<b.x;
}
return a.y<b.y;
}
inl meter(XY a,XY b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
void Divide(int st,int dr){
int mij,i,m,j;
inl aux;
if(dr-st<=2){
if(dr-st==1){
aux=meter(poit[st],poit[dr]);dist=dist>aux?aux:dist;
}else{
aux=meter(poit[st] , poit[dr]);dist=dist>aux?aux:dist;
aux=meter(poit[st+1], poit[dr]);dist=dist>aux?aux:dist;
aux=meter(poit[st] ,poit[st+1]);dist=dist>aux?aux:dist;
}
return;
}
mij=(st+dr)/2;
Divide(st,mij);
Divide(mij,dr);
m=0;
for(i=st;i<=dr;i++){
if((poit[mij].x-poit[i].x)*(poit[mij].x-poit[i].x)<=dist){
sir[m]=poit[i];
m++;
}
}
sort(sir,sir+m,ctr);
for(i=0;i<m;i++){
j=i+1;
aux=0;
while(j<m && aux<=dist){
aux=meter(poit[i],poit[j]);dist=dist>aux?aux:dist;
j++;
}
}
}
int main(){
int n,i;
fin=fopen("cmap.in","r");
fout=fopen("cmap.out","w");
n=Read();
for(i=0;i<n;i++){
poit[i]={Read(),Read()};
}
sort(poit,poit+n,cmp);
Divide(0,n-1);
fprintf(fout,"%.6f",(double)sqrt(dist));
fclose(fin);
fclose(fout);
return 0;
}