Pagini recente » Cod sursa (job #1537767) | Cod sursa (job #660329) | Cod sursa (job #1314351) | Cod sursa (job #1586421) | Cod sursa (job #2182274)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <limits.h>
#define lim 100010
using namespace std;
ifstream fin("cmap.in");
FILE *f=fopen("cmap.out","w");
//double maxLength;
int nFirst;
struct punct
{
int x,y;
}Y[lim],Z[lim];
bool sortConditionX(punct i,punct j)
{
if(i.x<j.x) return 1;
if(i.x==j.x && i.y<j.y) return 1;
return 0;
}
bool sortConditionY(punct i,punct j)
{
if(i.y<j.y) return 1;
if(i.y==j.y && i.x<j.x) return 1;
return 0;
}
void check(int n)
{
for(int i=1;i<=n;i++)
cout<<Y[i].x<<" "<<Y[i].y<<"\n";
cout<<"\n";
}
double cmap(int i,int n)
{
if(n==1)
{
return INT_MAX;
}
if(n==2)
{
if(Y[i].y>Y[i+1].y)
{
punct aux;
aux=Y[i];
Y[i]=Y[i+1];
Y[i+1]=aux;
}
return (Y[i].x-Y[i+1].x)*(Y[i].x-Y[i+1].x)+(Y[i].y-Y[i+1].y)*(Y[i].y-Y[i+1].y);
}
double dist1=cmap(i,n/2),dist2=cmap(i+n/2,n/2);
double distDiv=min(dist1,dist2);
merge(Y+i,Y+i+n/2,Y+i+n/2,Y+i+n,Z+i,sortConditionY);
int zs=n/2,zd=n/2;
while(zs>=1 && Y[n/2].x-Y[zs].x<=distDiv)
zs--;
while(zd<=nFirst && Y[zd].x-Y[n/2].x<=distDiv)
zd++;
///sort(Y+zs,Y+zd+1,sortConditionY);
for(int i=zs;i<=zd;i++)
{
double dist=0;
for(int k=1;k<8 && i+k<=zd;k++)
{
dist=(Y[i+k].x-Y[i].x)*(Y[i+k].x-Y[i].x)+(Y[i+k].y-Y[i].y)*(Y[i+k].y-Y[i].y);
if(dist<distDiv)distDiv=dist;
}
}
return distDiv;
}
int main()
{
int xmax=0,ymax=0;
fin>>nFirst;
for(int i=1;i<=nFirst;i++)
{
fin>>Y[i].x>>Y[i].y;
/*if(Y[i].x>xmax)xmax=Y[i].x;
if(Y[i].y>ymax)ymax=Y[i].y;*/
}
check(nFirst);
sort(Y,Y+nFirst,sortConditionX);
check(nFirst);
//maxLength=sqrt(xmax*xmax+ymax*ymax);
double distMin=cmap(1,nFirst);
fprintf(f,"%f",sqrt(distMin));
return 0;
}