Pagini recente » Cod sursa (job #463033) | Cod sursa (job #2802685) | Cod sursa (job #251449) | Cod sursa (job #1125818) | Cod sursa (job #2617558)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <limits>
using namespace std;
bool cmpX(pair<long long int, long long int> &a, pair<long long int, long long int> b)
{
return a.first < b.first;
}
bool cmpY(pair<long long int, long long int> &a, pair<long long int, long long int> b)
{
return a.second < b.second;
}
double dist(pair<long long int, long long int> &a, pair<long long int, long long int> &b)
{
return sqrt(pow(a.first - b.first, 2) + pow(a.second - b.second, 2));
}
double nSquaredSol(vector< pair<long long int, long long int> > &coordonate)
{
double minDist = numeric_limits<double>::max();
for (long long int i = 0; i < coordonate.size(); i++)
{
for (long long int j = i + 1; j < coordonate.size(); j++)
{
double d = dist(coordonate[i], coordonate[j]);
if (d != 0)
minDist = min(minDist, d);
}
}
return minDist;
}
double getMinDistFromStrip(vector<pair<long long int, long long int> > &strip, double d)
{
for (long long int i = 0; i < strip.size(); i++)
{
for (long long int j = i + 1; j < strip.size() && strip[j].second - strip[i].second < d; j++)
{
d = min(d, dist(strip[i], strip[j]));
}
}
return d;
}
void showVect(vector<pair<long long int, long long int> > &vec)
{
for (vector< pair<long long int, long long int> >::iterator p=vec.begin() ; p!=vec.end(); p++ )
{
cout << (*p).first << " " << (*p).second << "\n";
}
cout << "\n";
}
double solve(vector<pair<long long int, long long int> > &sortatX, vector<pair<long long int, long long int> > &sortatY)
{
if (sortatX.size() <= 3)
{
return nSquaredSol(sortatX);
}
pair<long long int, long long int> midPoint = sortatX[sortatX.size() / 2];
vector<pair<long long int, long long int> > sortatX_st;
vector<pair<long long int, long long int> > sortatX_dr;
vector<pair<long long int, long long int> > sortatY_st;
vector<pair<long long int, long long int> > sortatY_dr;
for (long long int i = 0; i < sortatY.size(); i++)
{
if (sortatX[i].first <= midPoint.first)
{
sortatX_st.push_back(sortatX[i]);
}
else
{
sortatX_dr.push_back(sortatX[i]);
}
if (sortatY[i].first <= midPoint.first)
{
sortatY_st.push_back(sortatY[i]);
}
else
{
sortatY_dr.push_back(sortatY[i]);
}
}
double distSt = solve(sortatX_st, sortatY_st);
double distDr = solve(sortatX_dr, sortatY_dr);
double d = min(distSt, distDr);
vector<pair<long long int, long long int> > strip;
for (long long int i = 0; i < sortatY.size(); i++)
{
if (abs(sortatY[i].first - midPoint.first) < d)
{
strip.push_back(sortatY[i]);
}
}
return min(d, getMinDistFromStrip(strip, d));
}
double nLognSol(vector<pair<long long int, long long int> > &coordonate)
{
vector<pair<long long int, long long int> > sortatX(coordonate);
vector<pair<long long int, long long int> > sortatY(coordonate);
sort(sortatX.begin(), sortatX.end(), cmpX);
sort(sortatY.begin(), sortatY.end(), cmpY);
return solve(sortatX, sortatY);
}
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int main()
{
long long int n;
fin >> n;
vector<pair<long long int, long long int> > coordonate(n);
for (long long int i = 0; i < n; i++)
{
long long int x, y;
fin >> x >> y;
coordonate[i].first = x;
coordonate[i].second = y;
}
double solutie = nLognSol(coordonate);
fout << fixed;
fout.precision(6);
fout << solutie;
return 0;
}