Pagini recente » Cod sursa (job #1051668) | Cod sursa (job #1616487) | Cod sursa (job #707612) | Cod sursa (job #2812825) | Cod sursa (job #2180951)
#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];
bool sortCondition(punct i,punct j)
{
if(i.x<j.x) return 1;
if(i.x==j.x && i.y<j.y) 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<=3)
{
double distMin=INT_MAX,dist=0;
for(int k=0;k<n;k++)
{
for(int l=k+1;l<n;l++)
{
dist=sqrt((Y[i+k].x-Y[i+l].x)*(Y[i+k].x-Y[i+l].x)+(Y[i+k].y-Y[i+l].y)*(Y[i+k].y-Y[i+l].y));
if(dist<distMin)distMin=dist;
}
}
return distMin;
}
double dist1=cmap(i,n/2),dist2=cmap(i+n/2,n/2);
double distDiv=min(dist1,dist2);
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++;
for(int i=zs;i<=zd;i++)
{
double dist=0;
for(int k=1;k<8;k++)
{
dist=sqrt((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,sortCondition);
check(nFirst);
//maxLength=sqrt(xmax*xmax+ymax*ymax);
double distMin=cmap(1,nFirst);
fprintf(f,"%f",distMin);
return 0;
}