Pagini recente » Cod sursa (job #2456248) | Cod sursa (job #1232255) | Cod sursa (job #2456257) | Cod sursa (job #1889398) | Cod sursa (job #2074008)
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
bool sortbysec(const pair<long long int,long long int> &a, const pair<long long int,long long int> &b){
return (a.second < b.second);
}
long double distEuclid(pair<long long int, long long int> p1, pair<long long int, long long int> p2){
return sqrt((p1.first-p2.first)*(p1.first-p2.first) + (p1.second-p2.second)*(p1.second-p2.second));
}
void interclaseaza(vector< pair<long long int, long long int> > Y, long long int st, long long int mij, long long int dr){
vector< pair<long long int, long long int> > Z;
long long int i = st, j = mij+1;
while (i <= mij && j <= dr){
if (Y[i].second <= Y[j].second){
Z.push_back(Y[i]);
i++;
}
else{
Z.push_back(Y[j]);
j++;
}
while(i <= mij){
Z.push_back(Y[i]);
i++;
}
while(j <= dr){
Z.push_back(Y[j]);
j++;
}
for (long long int i=st; i<=dr; i++)
Y[i] = Z[i-st];
}
}
long double DivImp(vector< pair<long long int, long long int> > X, vector< pair<long long int, long long int> > Y, long long int st, long long int dr){
if (dr - st + 1 < 4){
sort(Y.begin(), Y.end(), sortbysec);
long double minVal = distEuclid(X[st], X[dr]);
for (long long int i=st; i<=dr-1; i++)
for (long long int j=i+1; j<=dr; j++){
if (distEuclid(X[i], X[j]) < minVal)
minVal = distEuclid(X[i], X[j]);
}
return minVal;
}
else{
long long int mij = st + (dr - st)/2;
long double d1 = DivImp(X, Y, st, mij);
long double d2 = DivImp(X, Y, mij+1, dr);
long double d = min(d1, d2);
interclaseaza(Y, st, mij, dr);
vector< pair<long long int, long long int> > LY;
for (long long int i=st; i<=dr; i++){
if (abs(Y[i].first - X[mij].first) <= d)
LY.push_back(Y[i]);
}
long long int nr;
long double d3 = d;
for (long long int i=0; i<LY.size()-1; i++){
if (7 <= LY.size()-i)
nr = 7;
else nr = LY.size()-i;
for (long long int j=1; j<=nr; j++){
if(distEuclid(LY[i], LY[i+j]) < d3)
d3 = distEuclid(LY[i], LY[i+j]);
}
}
return d3;
}
}
int main()
{
fstream InputFile;
ofstream OutputFile;
long long int n;
pair<long long int, long long int> p;
vector< pair<long long int, long long int> > X;
vector< pair<long long int, long long int> > Y;
InputFile.open("cmap.in");
if (InputFile.is_open()){
InputFile >> n;
for (long long int i=0; i<n; i++){
InputFile >> p.first;
InputFile >> p.second;
X.push_back(p);
}
InputFile.close();
}
else cout << "The input file could not be opened.";
sort(X.begin(), X.end());
for (long long int i=0; i<X.size(); i++){
Y.push_back(X[i]);
}
OutputFile.open("cmap.out");
OutputFile << DivImp(X, Y, 0, n-1);
return 0;
}