Pagini recente » Cod sursa (job #996499) | Cod sursa (job #1002837) | Rating Lihet Briana (LihetBriana) | Cod sursa (job #1392913) | Cod sursa (job #664210)
Cod sursa(job #664210)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define MAX 100050
using namespace std;
int n, p[MAX];
struct punct
{
long long x, y;
}v[MAX];
bool cmpx(punct a, punct b)
{
return a.x < b.x;
}
bool cmpy(int a, int b)
{
return v[a].y < v[b].y;
}
double distanc(int i , int j)
{
double dist;
dist = (v[i].x - v[j].x) * (v[i].x - v[j].x);
dist += (v[i].y - v[j].y) * (v[i].y - v[j].y);
return sqrt(dist);
}
void citire()
{
//freopen("cmap.in", "r", stdin);
ifstream in("cmap.in");
in>>n;
for(int i = 1; i <= n; i++)
{
in>>v[i].x>>v[i].y;
}
in.close();
}
double min(double a, double b)
{
if(a < b)
return a;
return b;
}
double solve(int left, int right)
{
double minimumDistance;
if(right - left + 1 <= 3)
{
minimumDistance = distanc(left, right);
if(right - left == 2)
{
minimumDistance = min(minimumDistance, distanc(left + 1, right));
minimumDistance = min(minimumDistance, distanc(left, left + 1));
}
return minimumDistance;
}
int mij = (left + right) / 2;
minimumDistance = min(solve(left, mij), solve(mij + 1, right));
int k = 1;
for(int i = left; i <= right; i++)
{
if(abs(v[i].x - v[mij].x) <= minimumDistance)
{
p[k++] = i;
}
}
sort(p + 1, p + k, cmpy);
for(int i = 2, j = 1; i < k; i++)
{
while(v[ p[i]].y - v[ p[j]].y >= minimumDistance)
j++;
for(int h = j; h < i; h++)
{
minimumDistance = min(minimumDistance, distanc(p[h], p[i]));
}
}
return minimumDistance;
}
void afisare()
{
ofstream out("cmap.out");
out<<fixed<<setprecision(6)<<solve(1, n);
out.close();
}
int main()
{
citire();
sort(v + 1, v + n + 1, cmpx);
afisare();
return 0;
}