Pagini recente » Cod sursa (job #2965762) | Cod sursa (job #2786904) | Cod sursa (job #229961) | Cod sursa (job #213508) | Cod sursa (job #1016723)
#include<iostream>
#include<fstream>
#include<ctime>
#include<cstdlib>
#include<cmath>
#include<iomanip>
using namespace std;
long long x[10000], y[10000];
long long pivot(int left, int right)
{
long long p1,p2,p3,p,mini,maxi;
p1=x[left + rand() % (right-left+1)];
p2=x[left + rand() % (right-left+1)];
p3=x[left + rand() % (right-left+1)];
if(p1<=p2&&p1<=p3)
mini=p1;
if(p2<=p1&&p2<=p3)
mini=p2;
if(p3<=p1&&p3<=p2)
mini=p3;
if(p1>=p2&&p1>=p3)
maxi=p1;
if(p2>=p1&&p2>=p3)
maxi=p2;
if(p3>=p1&&p3>=p2)
maxi=p3;
p=p1+p2+p3-maxi-mini;
return p;
}
long long dist(int a, int b)
{
return ((x[b]-x[a])*(x[b]-x[a])+(y[b]-y[a])*(y[b]-y[a]));
}
void quicksort(int left, int right)
{
int i=left, j=right, tmp;
long long piv;
piv=pivot(left,right);
while(i<=j)
{
while(x[i]<piv)
i++;
while(x[j]>piv)
j--;
if(i<=j)
{
tmp=x[i];
x[i]=x[j];
x[j]=tmp;
tmp=y[i];
y[i]=y[j];
y[j]=tmp;
if(x[i]==x[j])
if(y[i]>y[j]){
tmp=y[i];
y[i]=y[j];
y[j]=tmp;
}
i++;
j--;
}
}
if(left<j)
quicksort(left,j);
if(i<right)
quicksort(i,right);
}
long long cmap(int left, int right)
{
long long a1, d, nr, nr1, nr2;
int t, k, a, b, c, mij, i, j;
if(left<=right)
{
if(left==right)
return 1000000000;
if(right-left==1)
return dist(left, right);
else if(right-left==2)
{
a=left;
b=left+1;
c=left+2;
nr=min(dist(a,b),dist(a,c));
nr=min(nr, dist(b,c));
}
else{
mij=(left+right)/2;
nr1=cmap(left, mij);
nr2=cmap(mij, right);
nr=min(nr1,nr2);
a1=x[mij];
i=mij-1;
j=mij+1;
while(a1-x[i]<=nr)
i--;
while(x[j]-a1<=nr)
j++;
i++;
j--;
for(t=i;t<=j-7;t++){
for(k=1;k<=7;k++)
{
d=dist(t,t+k);
if(d<nr && t<=mij && t+k>=mij)
nr=d;}
}
}
}
return nr;
}
int main()
{
int n, i;
ifstream f("cmap.in");
ofstream g("cmap.out");
f>>n;
for(i=0;i<n;i++)
f>>x[i]>>y[i];
quicksort(0,n-1);
g<<fixed<< setprecision(6) << sqrt(cmap(0,n-1));
}