Pagini recente » Cod sursa (job #1796132) | Cod sursa (job #457921) | Cod sursa (job #2108121) | Cod sursa (job #754444) | Cod sursa (job #1172799)
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
#define max 100001
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n;
struct point{
int x, y;
};
typedef struct point point;
point numbers[max];
point submult[max];
int inline compare_x(point a, point b){
return a.x <= b.x;
}
int inline compare_y(point a, point b){
return a.y <= b.y;
}
double inline dist(point a, point b){
return sqrt(pow((double)(b.x-a.x),2.)+
pow((double)(b.y-a.y),2.));
}
double inline combine(int i, int j, double delta){
int len = j - i + 1;
double v;
for(int k = 0; k < len; k++){
submult[k] = numbers[k+i];
}
sort(submult, submult+len, compare_y);
for(int k = 0; k < len; k++){
// optimizare pt cache
point *kk = submult+k;
for(int l = 1; l <= 7; l++){
if(k+l >= len) break;
if(delta > (v = dist(*kk, *(kk+l))))
delta = v;
}
}
return delta;
}
double inline find(int left, int right){
double d, delta;
int i, j;
int len = right-left+1;
if(len == 3){
return min(dist(numbers[left], numbers[left+1]), min(dist(numbers[left], numbers[left+2]), dist(numbers[left+1], numbers[left+2])));
}
if(len == 2)
return dist(numbers[left], numbers[left+1]);
d = numbers[left + len/2-1].x + (numbers[left + len/2].x - numbers[left + len/2 - 1].x)/2.;
delta = min(find(left, left+len/2-1),find(left + len/2, right));
i = left + len/2 -1;
while(i >= left && ((d - numbers[i].x) <= delta))
i--;
j = left + len/2;
while(j <= right && ((numbers[j].x - d) <= delta))
j++;
delta = combine(i+1, j-1, delta);
return delta;
}
int main(){
point p;
fin >> n;
for(int i = 0; i < n; i++){
fin >> p.x >> p.y;
numbers[i] = p;
}
/* sorted after x */
sort(numbers, numbers+n, compare_x);
fout << setprecision(6) << std::fixed << find(0, n-1);
return 0;
}