Pagini recente » Cod sursa (job #2325237) | Cod sursa (job #2630019) | Cod sursa (job #3261228) | Cod sursa (job #2672329) | Cod sursa (job #2657426)
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
int n,a[100002][2],i,j;
long double dist(int x, int y)
{
long long x1=a[x][0];
long long x2=a[y][0];
long long y1=a[x][1];
long long y2=a[y][1];
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][0]+a[mij+1][0])/2;
long double Smin=0.0;
Smin=cmap(st,mij);
Smin=min(Smin,cmap(mij+1,dr));
int xmin=vert-Smin;
int xmax=vert+Smin;
int st1=st;
int dr1=dr;
int mij1;
while(st1<=dr1)
{
mij1=(st1+dr1)/2;
if(a[mij1][0]<xmin)
{
st1=mij1+1;
}
else
{
if(a[mij1][0]>xmin)
{
dr1=mij1-1;
}
else
{
while(a[mij1][0]==xmin)
{
mij1--;
}
mij1++;
break;
}
}
}
int indminx;
if(st1>dr1)
{
if(st1<=st)
indminx=st1;
else
indminx=n+1;
}
else
{
indminx=mij1;
}
st1=st;
dr1=dr;
while(st1<=dr1)
{
mij1=(st1+dr1)/2;
if(a[mij1][0]<xmax)
{
st1=mij1+1;
}
else
{
if(a[mij1][0]>xmax)
{
dr1=mij1-1;
}
else
{
while(a[mij1][0]==xmax)
{
mij1--;
}
mij1++;
break;
}
}
}
int indmaxx;
if(st1>dr1)
{
if(dr1>=dr)
indmaxx=dr1;
else
indmaxx=0;
}
else
{
indmaxx=mij1;
}
int b[dr-st+3][2];
int p=0;
for(i=indminx;i<=indmaxx;i++)
{
b[p][0]=a[i][0];
b[p++][1]=a[i][1];
}
for(i=0;i<p;i++)
{
for(j=i+1;j<p+8;j++)
{
if(sqrt((b[i][0]-b[j][0])*(b[i][0]-b[j][0])+(b[i][1]-b[j][1])*(b[i][1]-b[j][1]))<Smin)
{
Smin=sqrt((b[i][0]-b[j][0])*(b[i][0]-b[j][0])+(b[i][1]-b[j][1])*(b[i][1]-b[j][1]));
}
}
}
//cout << "REZULTAT PTR: " << st << ' ' << dr << " : " << Smin << '\n';
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);
}
int main()
{
in >> n;
for(i=0;i<n;i++)
{
in >> a[i][0] >> a[i][1];
}
sortare_x(0,n-1);
/*for(i=10000;i<10002;i++)
{
cout << a[i][0] << ' ' << a[i][1] << '\n';
}*/
long double l=cmap(0,n-1);
out << fixed << setprecision(6) << l;
}