Pagini recente » Statistici sake geo (naslau) | Cod sursa (job #2731656) | Profil M@2Te4i | Istoria paginii runda/concurs_elf1/clasament | Cod sursa (job #1172785)
#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 compare_x(point a, point b){
return a.x <= b.x;
}
int compare_y(point a, point b){
return a.y <= b.y;
}
double dist(int a, int b, int who){ // who = 0 pt numbers 1 pt submult
if (who == 0)
return (double)(numbers[b].x-numbers[a].x) * (double)(numbers[b].x-numbers[a].x) +
(double)(numbers[b].y-numbers[a].y) * (double)(numbers[b].y-numbers[a].y);
return (double)(submult[b].x-submult[a].x) * (double)(submult[b].x-submult[a].x) +
(double)(submult[b].y-submult[a].y) * (double)(submult[b].y-submult[a].y);
}
double combine(int i, int j, double delta){
int len = j - i + 1;
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++){
for(int l = 1; l <= 7; l++){
if(k+l >= len) break;
delta = min(delta, dist(k, k+l,1));
}
}
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(left, left+1,0), min(dist(left, left+2,0), dist(left+1, left+2,0)));
if(len == 2)
return dist(left, left+1,0);
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 << sqrt(find(0, n-1));
return 0;
}