Pagini recente » Cod sursa (job #1581728) | Cod sursa (job #1796128) | Cod sursa (job #1182261) | Cod sursa (job #2854261) | Cod sursa (job #2079888)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define INF 1<<30
using namespace std;
struct coord {
long 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&);
long double calc_dist(coord, coord);
long double pereche_minima() { return Divide(0, n-1); }
long double Divide(int, int);
};
long double Plan::Divide(int st, int dr)
{
long double d = INF, d1, d2, d3;
if(dr - st < 4) {
// for(int i=st; i<=dr; i++) cout<<Y[i].x<<" "<<Y[i].y<<"\n";
// cout<<"\n";
sort(Y.begin()+st, Y.begin()+dr+1, compy);
// for(int i=st; i<=dr; i++) cout<<Y[i].x<<" "<<Y[i].y<<"\n";
// cout<<"\n\n";
// 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]) );
// }
for(int i=st; i<dr; i++)
{
for(int j=i+1; j<=dr; j++)
{
d3 = calc_dist(X[i], X[j]);
d = min(d, d3);
}
}
} else {
int mij = (st + dr)/2, j, i;
d1 = Divide(st, mij);
d2 = Divide(mij+1, dr);
d3 = d = min( d1, d2 );
//Interclasare
// for(i=st; i<=dr; i++) cout<<Y[i].x<<" "<<Y[i].y<<"\n";
// cout<<"\n";
inplace_merge( Y.begin()+st, Y.begin()+mij+1, Y.begin()+dr+1, compy );
// for(i=st; i<=dr; i++) cout<<Y[i].x<<" "<<Y[i].y<<"\n";
// cout<<"\n\n";
//
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++)
{
long double daux = calc_dist( LY[i], LY[j] );
if( daux < d3 ) d3 = daux;
}
d = min( d, d3 );
//cout<<"sal";
}
return d;
}
long double Plan::calc_dist(coord A, coord B) {
return sqrtl( (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);
for(int i=0; i<X.size(); i++) cout<<X[i].x<<" "<<X[i].y<<"\n";
cout<<"\n";
//for(int i=0; i<Y.size(); i++) cout<<Y[i].x<<" "<<Y[i].y<<"\n";
}
int main()
{
ifstream fin("cmap.in");
ofstream fout("cmap.out");
Plan plan(fin);
fin.close();
fout << setprecision(10) << plan.pereche_minima();
fout.close();
return 0;
}