Pagini recente » Cod sursa (job #1729035) | Cod sursa (job #2400094) | Cod sursa (job #299573) | Cod sursa (job #2114945) | Cod sursa (job #2072639)
#include <iostream>
#include <fstream>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct punct
{
int x,y;
}P[100];
double distanta(punct a,punct b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmpX(punct a,punct b)
{
return a.x<b.x;
}
bool cmpY(punct a,punct b)
{
return a.y<=b.y;
}
struct minima
{
double dis;
punct p1,p2;
};
minima mini;
minima dist_min(int st,int dr,punct P[])
{
if((dr-st+1)<=3)
{
if((dr-st+1)==3)
{
if(distanta(P[st],P[st+1])<distanta(P[st],P[dr]))
{
mini.dis=distanta(P[st],P[st+1]);
mini.p1=P[st];
mini.p2=P[st+1];
}
else
{
mini.dis=distanta(P[st],P[dr]);
mini.p1=P[st];
mini.p2=P[dr];
}
if(distanta(P[st+1],P[dr])<mini.dis)
{
mini.dis=distanta(P[st+1],P[dr]);
mini.p1=P[st+1];
mini.p2=P[dr];
}
}
else
if((dr-st+1)==2)
{
mini.dis=distanta(P[st],P[dr]);
mini.p1=P[st];
mini.p2=P[dr];
}
return mini;
}
else
{
int d;
minima min_st,min_dr,min_p,min_p1;
punct Y[100];
int k=0;
min_p1.dis=1000000001;
d=(st+dr)/2;
min_st=dist_min(st,d,P);
min_dr=dist_min(d+1,dr,P);
if(min_st.dis<min_dr.dis)
min_p=min_st;
else
min_p=min_dr;
int i,j;
double l;
for(i=st;i<=dr;i++)
{
l=distanta(P[i],P[d]);
if(l<=min_p.dis)
{
Y[k]=P[i];
k++;
}
}
//set <punct>::iterator i,j;
sort(Y,Y+k,cmpY);
for(i=0;i<k-1;i++)
{
for(j=i+1;j<k;j++)
if(distanta(Y[i],Y[j])<min_p.dis)
{
min_p1.dis=distanta(Y[i],Y[j]);
min_p1.p1=Y[i];
min_p1.p2=Y[j];
}
}
if(min_p1.dis<min_p.dis)
{
min_p=min_p1;
}
return min_p;
}
}
int main()
{
int i,n;
punct p;
minima pct;
//vector <punct> P;
f>>n;
for(i=0;i<n;i++)
{
f>>P[i].x>>P[i].y;
}
pct=dist_min(0,n-1,P);
g<<pct.dis;//<<endl<<pct.p1.x<<" "<<pct.p1.y<<endl<<pct.p2.x<<" "<<pct.p2.y;
g.close();
return 0;
}