1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| #include <bits/stdc++.h>
#define ll long long
#define int long long
#define double long double
#define Orz ios::sync_with_stdio(0),cin.tie(0)
#define N 10002
#define INF 5e18
#define FOR(i,n) for(int i=0;i<n;i++)
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define pii pair<int,int>
#define x first
#define y second
#define pid pair<int,double>
#define pdi pair<double,int>
#define pdd pair<double,double>
using namespace std;
int n;
vector<pii> p,temp;
void init(){
cout<<fixed<<setprecision(4);
temp.clear();
p.assign(n,{0,0});
}
bool cmp(pii a,pii b){
return a.y < b.y;
}
double dis(pii a,pii b){
double x1 = a.x-b.x,y1 = a.y-b.y;
return sqrt(x1 * x1 + y1 * y1);
}
double solve(int l,int r){
if(l == r)return INF;
int mid = (l+r)/2,mid_pos = p[mid].x;;
double ans = min(solve(l,mid),solve(mid+1,r));
temp.assign((r-l+1),{0,0});
merge(
p.begin() + l, p.begin() + mid + 1,
p.begin() + mid + 1, p.begin() + r + 1,
temp.begin(), cmp
);
rep(i, l, r)p[i] = temp[i-l];
temp.clear();
rep(i, l, r){
if(abs(p[i].x - mid_pos) <= ans)
temp.push_back(p[i]);
}
int len = temp.size();
rep(i, 0, len-1){
rep(j, i+1, len-1){
ans = min(ans, dis(temp[i],temp[j]));
if(abs(temp[i].y-temp[j].y) > ans)
break;
}
}
return ans;
}
signed main(){
Orz;
while(cin>>n){
if(n==0)break;
init();
rep(i,0,n-1)cin>>p[i].x>>p[i].y;
sort(p.begin(),p.end());
double ans = solve(0,n-1);
if(ans > 10000)cout<<"INFINITY"<<endl;
else cout<<ans<<endl;
}
}
|