Pagini recente » Cod sursa (job #2653861) | Cod sursa (job #2654260) | Cod sursa (job #2656308) | Cod sursa (job #2653710) | Cod sursa (job #2659911)
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
struct punct{long long x, y;};
punct a[100002],b[100002];
int n,i,j;
bool compy(punct a,punct b)
{
if(a.y<b.y)
return 1;
if(a.y==b.y)
{
if(a.x<b.x)
return 1;
}
return 0;
}
long double dist(int x, int y)
{
long long x1=a[x].x;
long long x2=a[y].x;
long long y1=a[x].y;
long long y2=a[y].y;
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
long double cmap(int st,int dr)
{
//cout << "SE RULEAZA: " << st << ' ' << dr << '\n';
if(dr-st<3)
{
long double S=1000000000.0;
for(int m=st;m<=dr;m++)
{
for(int p=m+1;p<=dr;p++)
{
long double d=dist(p,m);
if(d<S)
{
S=d;
}
}
}
//cout << "REZULTAT PTR: " << st << ' ' << dr << " : " << S << '\n';
return S;
}
int mij=(st+dr)/2;
int vert=a[mij].x;
long double Smin=0.0;
Smin=cmap(st,mij);
Smin=min(Smin,cmap(mij+1,dr));
int ps,pd;
for(ps=mij;ps>=st;ps--)
{
if(vert-a[ps].x>=Smin)
{
break;
}
}
ps++;
for(pd=mij;pd<=dr;pd++)
{
if(a[pd].x-vert>=Smin)
{
break;
}
}
pd--;
for(int i=ps;i<=pd;i++)
{
b[i]=a[i];
}
sort(b+ps,b+pd+1,compy);
for(int i=ps;i<pd;i++)
{
for(int j=i+1;j<=min(i+7,pd);j++)
{
if(dist(i,j)<Smin)
{
Smin=dist(i,j);
}
}
}
return Smin;
}
/*int partitionare(int st, int dr)
{
int i=st,j=dr,s=1;
while(i<j)
{
if(a[i][0]>a[j][0])
{
swap(a[i][0],a[j][0]);
swap(a[i][1],a[j][1]);
s=-s;
}
if(s==1)
i++;
else
j--;
}
return i;
}
void sortare_x(int st, int dr)
{
if(st>=dr)
return;
int p=partitionare(st,dr);
sortare_x(st,p-1);
sortare_x(p+1,dr);
}*/
bool compx(punct a,punct b)
{
if(a.x<b.x)
return 1;
if(a.x==b.x)
{
if(a.y<b.y)
return 1;
}
return 0;
}
int main()
{
in >> n;
for(i=0;i<n;i++)
{
in >> a[i].x >> a[i].y;
}
//sortare_x(0,n-1);
sort(a,a+n,compx);
long double l=cmap(0,n-1);
out << fixed << setprecision(6) << l;
}