Pagini recente » Cod sursa (job #554110) | Cod sursa (job #1670301) | Cod sursa (job #1084135) | Cod sursa (job #2427361) | Cod sursa (job #1302498)
#include <fstream>
#include <algorithm>
#include <math.h>
#include <iomanip>
#define NMax 100001
#define INF 2000000000
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
int n, i, j;
struct punct
{
int x;
int y;
}point[NMax], tmp[NMax], midpoint[NMax];
bool cmp(const punct &p1, const punct &p2)
{
return p1.x < p2.x;
}
double dist(punct p1, punct p2)
{
return sqrt((double)((long long)((long long)p1.x-p2.x)*(p1.x-p2.x)+(long long)((long long)p1.y-p2.y)*(p1.y-p2.y)));
}
double divimp(int st, int dr)
{
int mid=(st+dr)/2;
if (st>=dr)
return INF;
if (dr-st == 1) {
if (point[st].y > point[dr].y) {
swap (point[st], point[dr]);
punct tm;
tm=point[st];
point[st]=point[dr];
point[dr]=tm;
}
return dist(point[st], point[dr]);
}
int midlane=point[mid].x;
double d_st=divimp(st, mid);
double d_dr=divimp(mid+1, dr);
double dmin=min(d_st, d_dr);
int ind=0, ind1, ind2;
for (ind1=st, ind2=mid+1; ind1 <= mid && ind2 <= dr; ) {
if (point[ind1].y < point[ind2].y)
tmp[++ind]=point[ind1++];
else
tmp[++ind]=point[ind2++];
}
for (; ind1<=mid ; ind1++)
tmp[++ind]=point[ind1];
for (; ind2<=dr; ind2++)
tmp[++ind]=point[ind2];
int k=0;
ind=0;
for (i=st; i<=dr; i++) {
point[i]=tmp[++ind];
if (abs(midlane-point[i].x) <= dmin)
midpoint[++k]=point[i];
}
double Min=INF;
for (i=1; i<=k; i++)
for (j=i-1; j>=i-6 && j > 0; j--)
Min = min(Min, dist(midpoint[i], midpoint[j]));
return min(Min, dmin);
}
int main()
{
f>>n;
for (i=1; i<=n; i++)
f>>point[i].x>>point[i].y;
sort (point+1, point+n+1, cmp);
double sol=divimp(1, n);
g<<fixed<<setprecision(6)<<sol;
return 0;
}