Pagini recente » Cod sursa (job #2840275) | Cod sursa (job #499055) | Cod sursa (job #1419296) | Cod sursa (job #2547939) | Cod sursa (job #988126)
Cod sursa(job #988126)
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
using namespace std;
const string file = "cmap";
const string infile = file + ".in";
const string outfile = file + ".out";
typedef long long int64;
int N;
struct Point2D
{
int x;
int y;
};
int predXY(const Point2D& a, const Point2D& b)
{
if(a.x != b.x)
{
return a.x < b.x;
}
else
{
return a.y < b.y;
}
}
int predYX(const Point2D& a, const Point2D& b)
{
if(a.y != b.y)
{
return a.y < b.y;
}
else
{
return a.x < b.x;
}
}
int64 dist(const Point2D& a, const Point2D& b)
{
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
vector<Point2D> pointsX;
vector<Point2D> pointsY;
vector<Point2D> centered;
const int64 INF = 1LL<<62;
int64 Closest(int st, int dr)
{
if(st >= dr) return INF;
else if(dr - st == 1)
{
sort(pointsY.begin() + st, pointsY.begin() + dr + 1, predYX);
return dist( pointsX[st], pointsX[dr]);
}
int mij = (dr - st)/2 + st;
int64 minimum = min(Closest(st, mij), Closest(mij + 1, dr));
sort(pointsY.begin() + st, pointsY.begin() + dr + 1, predYX);
int cSize = 0;
for(vector<Point2D>::iterator itr = pointsY.begin() + st;
itr != pointsY.begin() + dr + 1;
itr++)
{
if(abs(itr->x - pointsX[mij].x) <= minimum)
{
centered[cSize++] = *itr;
}
}
for(int i = 0; i < cSize; i++)
{
for(int j = i + 1; j < cSize && j < i + 8 ; j++)
{
minimum = min(minimum, dist(centered[i], centered[j]));
}
}
return minimum;
}
int main()
{
fstream fin(infile.c_str(), ios::in);
fin >> N;
pointsX.resize(N);
pointsY.resize(N);
centered.resize(N);
for(int i = 0; i < N; i++)
{
int x, y;
fin >> x >> y;
pointsX[i].x = pointsY[i].x = x;
pointsX[i].y = pointsY[i].y = y;
}
fin.close();
sort(pointsX.begin(), pointsX.end(), predXY);
fstream fout(outfile.c_str(), ios::out);
fout << fixed << setprecision(6) << sqrt(Closest(0, N - 1)) << "\n";
fout.close();
}