Pagini recente » Cod sursa (job #2151090) | Cod sursa (job #3140366) | Cod sursa (job #1483784) | Cod sursa (job #1278546) | Cod sursa (job #2074053)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
struct coord {
double x, y;
};
bool compx(coord A, coord B) {
if( A.x == B.x ) return ( A.y < B.y );
return ( A.x < B.x );
}
bool compy(coord A, coord B) {
return ( A.y < B.y );
}
class Plan
{
int n;
vector<coord> X, Y;
public:
Plan(ifstream&);
double calc_dist(coord, coord);
double pereche_minima() { return Divide(0, n-1); }
double Divide(int, int);
};
double Plan::Divide(int st, int dr)
{
double d, d1, d2, d3;
if(dr - st < 4) {
sort(Y.begin()+st, Y.begin()+st+dr-1, compy);
d = min( calc_dist(X[st], X[st+1]), calc_dist(X[st], X[st+2]) );
d = min( d, calc_dist(X[st+1], X[st+2]) );
if(dr - st == 3) {
d = min( d, calc_dist(X[st], X[st+3]) );
d = min( d, calc_dist(X[st+1], X[st+3]) );
d = min( d, calc_dist(X[st+2], X[st+3]) );
}
} else {
int mij = (st + dr)/2;
d1 = Divide(st, mij);
d2 = Divide(mij+1, dr);
d3 = d = min( d1, d2 );
//Interclasare
vector<coord> aux(Y.begin()+st, Y.begin()+st+dr);
int i = st, j = mij+1, contor = st;
while(i <= mij && j <= dr) {
if( aux[i].y < aux[j].y ) Y[contor++] = aux[i++];
else Y[contor++] = aux[j++];
}
while(i <= mij) Y[contor++] = aux[i++];
while(j <= dr) Y[contor++] = aux[j++];
//
vector<coord> LY;
for(i = st; i <= dr; i++)
if( abs( X[mij].x - Y[i].x ) <= d ) LY.push_back( Y[i] );
for(i = 0; i<LY.size()-1; i++)
for(j=i+1; j<LY.size() && ( LY[j].y - LY[i].y < d3 ); j++)
if( calc_dist( LY[i], LY[j] ) < d3 ) d3 = calc_dist( LY[i], LY[j] );
d = min( d, d3 );
//cout<<"sal";
}
return d;
}
double Plan::calc_dist(coord A, coord B) {
return sqrt( (B.x - A.x)*(B.x - A.x) + (B.y - A.y)*(B.y - A.y) );
}
Plan::Plan(ifstream& fin)
{
fin>>n;
for(int i=1; i<=n; i++)
{
coord aux;
fin>>aux.x>>aux.y;
X.push_back(aux);
Y.push_back(aux);
}
sort(X.begin(), X.end(), compx);
sort(Y.begin(), Y.end(), compx);
}
int main()
{
ifstream fin("cmap.in");
ofstream fout("cmap.out");
Plan plan(fin);
fin.close();
fout<<plan.pereche_minima();
fout.close();
return 0;
}