Pagini recente » Cod sursa (job #714411) | Cod sursa (job #1075198) | Cod sursa (job #2872700) | Cod sursa (job #1024379) | Cod sursa (job #479555)
Cod sursa(job #479555)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
const int BUFSIZE = 1000000;
char buf[BUFSIZE];
ifstream cin("cmap.in");
ofstream cout("cmap.out");
typedef pair<int, int> point;
#define y first
#define x second
inline double dist(const point &a, const point &b)
{
return sqrt((double)(a.x - b.x)*(double)(a.x - b.x) + (double)(a.y - b.y)*(double)(a.y - b.y));
}
double distOnLine(const vector<point> &p)
{
double best = dist(p[0], p[1]), temp;
for(unsigned int i=2;i<p.size();++i)
{
temp = dist(p[i - 1], p[i]);
if(temp < best)
best = temp;
}
return best;
}
double distBrut(const vector<point> &p)
{
double best = dist(p[0], p[1]), temp;
for(unsigned int i=0;i<p.size();++i)
for(int j=i+1;j<p.size();++j)
if((temp = dist(p[i], p[j])) < best)
best = temp;
return best;
}
double dist(const vector<point> &p, int min, int max)
{
if (p.size() < 2)
return 1e20;
if (p.size() < 5)
return distBrut(p);
if(min == max)
return distOnLine(p);
int mij = (min + max) / 2;
vector<point> left, right;
for(unsigned int i=0;i<p.size();++i)
if(p[i].x <= mij)
left.push_back(p[i]);
else
right.push_back(p[i]);
double dl = dist(left, min, mij),
dr = dist(right, mij + 1, max);
left.clear(), right.clear();
double d = std::min(dl, dr);
for(unsigned int i=0;i<p.size();++i)
if(abs(p[i].x - mij) < d)
left.push_back(p[i]);
double temp;
for(unsigned int i=0;i<left.size();++i)
{
for (unsigned int j = i + 1; j < left.size() && p[i].y + d > p[j].y; ++ j)
if ((temp = dist(p[i], p[j])) < d)
d = temp;
}
return d;
}
int main()
{
cin.rdbuf()->pubsetbuf(buf, BUFSIZE);
int n, min = 0x7fffffff, max = 0x8fffffff;
cin >> n;
vector<point> p(n);
for(int i=0;i<n;++i)
{
cin >> p[i].x >> p[i].y;
if(p[i].x < min)
min = p[i].x;
if(p[i].x > max)
max = p[i].x;
}
std::sort(p.begin(), p.end());
double d = dist(p, min, max);
cout << setprecision(20) << d << endl;
return 0;
}