Pagini recente » Cod sursa (job #1548641) | Cod sursa (job #1409747) | Cod sursa (job #1098926) | Cod sursa (job #2638858) | Cod sursa (job #3225285)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int NMax = 100000;
pair<int, int> v[NMax + 10];
pair<int, int> tmp[NMax + 10];
int N;
double distanta(int x, int y){
int x2 = v[y].first, x1 = v[x].first;
int y2 = v[y].second, y1 = v[x].second;
return sqrt((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1));
}
double solve(int st, int dr){
if(st == dr){
return 0;
}
else{
int mij = (st + dr) / 2;
double s1 = solve(st, mij);
double s2 = solve(mij + 1, dr);
if(s1 == 0){
s1 = distanta(st, st + 1);
}
if(s2 == 0){
s2 = distanta(dr - 1, dr);
}
double d = min(s1, s2);
int k = st, i = st, j = mij + 1;
while(i <= mij && j <= dr){
if(v[i].second < v[j].second){
tmp[k ++] = v[i ++];
}
else{
tmp[k ++] = v[j ++];
}
}
while(i <= mij){
tmp[k ++] = v[i ++];
}
while(j <= dr){
tmp[k ++] = v[j ++];
}
for(int i=st; i<=dr; ++i){
v[i] = tmp[i];
}
i = mij - 1;
vector<int> v;
while(distanta(mij, i) <= d && i > 0){
v.push_back(i);
-- i;
}
i = mij + 1;
while(distanta(mij, i) <= d && i <= N){
v.push_back(i);
++ i;
}
for(int i=0; i<v.size(); ++i){
for(int j=i+1; j<v.size(); ++j){
d = min(d, distanta(i, j));
}
}
cout << st << ' ' << dr << ' ' << d << '\n';
return d;
}
}
int main()
{
fin >> N;
for(int i=1; i<=N; ++i){
fin >> v[i].first >> v[i].second;
}
sort(v + 1, v + N + 1);
fout << setprecision(10) << solve(1, N) << '\n';
return 0;
}