Pagini recente » Cod sursa (job #600494) | Cod sursa (job #3251739) | Cod sursa (job #84099) | Cod sursa (job #646334) | Cod sursa (job #2134318)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
//#include "grafic.h"
#include <limits>
#include <set>
#include <math.h>
#include <iomanip>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct pair_double{
double first, second;
};
vector<pair_double> vec;
int n;
double x, y, a;
double dist(pair_double a, pair_double b){
return sqrt(pow(a.first - b.first, 2) + pow(a.second - b.second, 2));
}
bool cmp(pair_double a, pair_double b){
bool ch = false;
if(a.first < b.first)
ch = true;
else if(a.first == b.first && a.second < b.second)
ch = true;
return ch;
}
int left_poz(int mid, double value)
{
int i = mid;
while(i >= 0 && vec[i].first >= value)
{
i--;
}
return ++i;
}
int right_poz(int mid, double value)
{
int i = mid + 1;
while(i < n && vec[i].first <= value)
{
i++;
}
return --i;
}
double MinDist(int mid, double value1, double value2)
{
int left = left_poz(mid, value1);
int right = right_poz(mid, value2);
double minim = numeric_limits<double>::max(), current;
for(int i = left; i <= mid; i++){
for(int j = mid + 1; j <= right; j++){
current = dist(vec[i], vec[j]);
if(minim > current)
minim = current;
}
}
return minim;
}
double res(int start, int stop)
{
if (stop - start + 1 <= 3)
{
double minim = numeric_limits<double>::max();
for (int i = start; i < stop; i++)
{
a = dist(vec[i], vec[i + 1]);
if (minim > a)
minim = a;
}
return minim;
}
else if(stop - start + 1 > 3)
{
int mid = start + (stop - start) / 2;
double drept = vec[mid].first + (vec[mid + 1].first - vec[mid].first) / 2;
double minim = min(res(start, mid), res(mid + 1, stop));
double current = MinDist(mid, drept - minim, drept + minim);
if(minim > current)
minim = current;
return minim;
}
}
int main()
{
fin >> n;
pair_double aux;
for (int i = 0; i < n; i++)
{
fin >> aux.first >> aux.second;
vec.push_back(aux);
}
sort(vec.begin(), vec.end(), cmp);
//cout << "rs: " << right_poz(5, 92) << "\n";
fout << setprecision(8) << res(0, n - 1) << "\n";
/*
for(int i = 0; i < n; i++){
cout << vec[i].first << " " << vec[i].second << "\n";
}
*/
return 0;
}