Pagini recente » Cod sursa (job #2693934) | Cod sursa (job #885129) | Cod sursa (job #824853) | Monitorul de evaluare | Cod sursa (job #2073363)
#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;
};
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;
double dist_min(int st,int dr,vector<punct> &P,vector<punct> &Y)
{
if((dr-st)==1)
{
double m;
m=2147483647;
//m.p1.x=2147483647;
//m.p1.y=2147483647;
// m.p1.x=-2147483647;
//m.p1.y=-2147483647;
return m;
}
else if((dr-st)==2)
{
double m;
if(Y[st].y>Y[dr].y)
swap(Y[st],Y[dr]);
m=distanta(P[0],P[1]);
// m.p1=P[0];
//m.p2=P[1];
return m;
}
int d;
double min_st,min_dr,min_p,min_p1;
// min_p1.dis=1000000001;
d=(st+dr)/2;
min_st=dist_min(st,d,P,Y);
min_dr=dist_min(d+1,dr,P,Y);
if(min_st<min_dr)
min_p=min_st;
else
min_p=min_dr;
vector <punct> aux(dr-st);
merge(Y.begin()+st,Y.begin()+d,Y.begin()+d,Y.begin()+dr,aux.begin(),cmpY);
copy(aux.begin(),aux.begin()+(dr-st),Y.begin()+st);
vector <punct> b;
for (int i = st; i < dr; i++)
{
if (abs(Y[i].x - P[d].x) <= min_p)
b.push_back(Y[i]);
}
/// verificarea benzii
double min_t = min_p;
for (int i = 0; i<b.size(); i++)
for (int j = i + 1; j < b.size() && b[j].y - b[i].y <= min_p; j++)
{
double c = distanta(b[i], b[j]);
if (c < min_t)
{
min_t= c;
}
}
return min_t;
/*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;
double pct;
f>>n;
vector<punct> P(n);
for(i=0; i<n; i++)
{
f>>P[i].x>>P[i].y;
}
sort(P.begin(),P.end(),cmpX);
vector <punct> Y;
Y=P;
pct=dist_min(0,n-1,P,Y);
g<<pct<<endl;/*<<pct.p1.x<<" "<<pct.p1.y<<endl<<pct.p2.x<<" "<<pct.p2.y;*/
return 0;
}