Pagini recente » Cod sursa (job #388653) | Cod sursa (job #1047538) | Cod sursa (job #2550881) | Cod sursa (job #1519628) | Cod sursa (job #2464699)
#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, rez;
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 FindMinDist(int in, int sf) {
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]);
}
}
}
if(n <= 3)
for(i = 1; i < n; i++)
for(j = i+1; j <= n; j++)
dmin = min(rez, Dist(i, j));
else {
dmin = min(FindMinDist(1, n/2), FindMinDist(n/2+1, n));
if(n%2 == 1)
dpos = double(punct[n/2+1].x);
else dpos = double(punct[n/2].x + punct[n/2+1].x)/2;
for(i = 1; i <= n; 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++) {
dmin = min(dmin, fDist(i, j));
}
}
}
g << fixed << setprecision(6) << dmin;
return 0;
}