Pagini recente » Cod sursa (job #2343323) | Cod sursa (job #1132229) | Cod sursa (job #840755) | Cod sursa (job #1961500) | Cod sursa (job #2680690)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <climits>
using namespace std;
typedef long long ll;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const ll INF = LONG_LONG_MAX;
struct point
{
ll x, y;
};
bool cmpx(point a, point b)
{
return a.x <= b.x;
}
bool cmpy(point a, point b)
{
return a.y <= b.y;
}
ll dist(point a, point b)
{
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
ll recur(vector<point> px, vector<point> py)
{
if(px.size() <=3)
{
ll dmin = INF;
for(int i=0; i < px.size()-1; i++){
for(int j =i + 1; j < px.size(); j++)
dmin = min(dmin, dist(px[i], px[j]));
}
return dmin;
}
int n = px.size();
int median = n >>1;
vector <point> drx;
vector <point> dry;
vector <point> stx;
vector <point> sty;
for(int i =0; i < px.size(); i++)
{
point p = px[i];
if(i < median)
stx.push_back(p);
else
drx.push_back(p);
}
ll xl = stx[stx.size() -1 ].x;
for(int i =0; i < py.size(); i++)
{
point p = py[i];
if(p.x <= xl)
sty.push_back(p);
else dry.push_back(p);
}
ll dmin = min( recur(drx, dry), recur(stx, sty));
vector <point> s;
for(int i =0; i < py.size(); i++)
{
if(abs(py[i].x - xl)<=dmin)
s.push_back(py[i]);
}
for(int i =0; i < s.size(); i++){
point p = s[i];
for(int j = i + 1; j < s.size() ; j++)
{
if(s[j].y - p.y > dmin)
break;
dmin = min(dmin, dist(p, s[j]));
}
}
return dmin;
}
int main()
{
int n, i;
ll x, y;
point a;
fin>>n;
vector <point> px;
vector <point> py;
for(i=1;i<=n;i++)
{
fin>>x>>y;
a.x = x;
a.y = y;
px.push_back(a);
py.push_back(a);
}
sort(px.begin(), px.end(), cmpx);
sort(py.begin(), py.end(), cmpy);
ll soll = recur(px,py);
double sol = sqrt((double) soll);
fout<<fixed<<showpoint;
fout<<setprecision(17);
fout<<sol<<"\n";
return 0;
}