Pagini recente » Istoria paginii runda/ah8/clasament | Istoria paginii runda/newcomers_2/clasament | Rating Anghelescu Matei (matei124) | Cod sursa (job #981580) | Cod sursa (job #1172795)
#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, v;
int i, j;
int len = right-left+1;
if(len == 3){
double d1 = dist(numbers[left], numbers[left+1]);
double d2 = dist(numbers[left], numbers[left+2]);
double d3 = dist(numbers[left+1], numbers[left+2]);
if(d1 > d2)
d1 = d2;
if(d1 > d3)
d1 = d3;
return d1;
}
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 = find(left, left+len/2-1);
if(delta > (v = find(left + len/2, right)))
delta = v;
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;
}