Pagini recente » Cod sursa (job #1246403) | Cod sursa (job #1006594) | Cod sursa (job #2746817) | Cod sursa (job #1020937) | Cod sursa (job #2464743)
#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include<bits/stdc++.h>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
#define MAX_SIZE 100001
int n, i, j, pos;
double dpos;
double dist, dmin;
struct Punct {
int x, y;
} punct[MAX_SIZE], fpunct[MAX_SIZE];
double Dist(int i, int j) {
return sqrt(pow(punct[i].x-punct[j].x, 2) + pow(punct[i].y-punct[j].y, 2));
}
double fDist(int i, int j) {
return sqrt(pow(fpunct[i].x-fpunct[j].x, 2) + pow(fpunct[i].y-fpunct[j].y, 2));
}
double Recursivitate(int in, int sf) {
int dif = sf-in+1;
int sum = sf+in;
if(dif > 255) {
dmin = min(Recursivitate(in, sum/2), Recursivitate(sum/2+1, sf));
if(dif%2 == 1)
dpos = double(punct[in+dif/2+1].x);
else dpos = double(punct[in+dif/2].x + punct[in+dif+1].x)/2;
pos = 0;
for(i = in; i <= sf; i++) {
if(abs(punct[i].x - dpos) < dmin) {
fpunct[++pos] = punct[i];
for(i = 1; i < pos; i++)
for(j = i+1; j <= pos; j++)
if(fpunct[i].y > fpunct[j].y)
swap(fpunct[i], fpunct[j]);
for(i = 1; i < pos; i++)
for(j = i+1; j <= i+7 && j <= pos; j++)
dmin = min(dmin, fDist(i, j));
}
else {
dmin = LONG_MAX;
for(i = in; i < sf; i++)
for(j = i+1; j <= sf; j++)
dmin = min(dmin, Dist(i, j));
}
return dmin;
}
int main()
{
dmin = LONG_MAX;
f >> n;
for(i = 1; i <= n; i++)
f >> punct[i].x >> punct[i].y;
for(i = 1; i < n; i++)
for(j = i+1; j <= n; j++)
if(punct[i].x > punct[j].x)
swap(punct[i], punct[j]);
g << fixed << setprecision(6) << Recursivitate(1, n);
return 0;
}