Pagini recente » Cod sursa (job #1113047) | Cod sursa (job #3191663) | Cod sursa (job #903968) | Cod sursa (job #1943363) | Cod sursa (job #2074019)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
class punct{
int x;
int y;
public:
punct() {x = 0; y = 0;}
punct(int abs, int ord){x = abs; y = ord;}
friend struct comparex;
friend struct comparey;
friend double dist(const punct &p1, const punct &p2);
friend istream& operator>>(istream& in, punct &p){
in >> p.x >> p.y;
return in;
}
friend ostream& operator<<(ostream& out, const punct &p){
out << p.x << ' ' << p.y;
return out;
}
punct& operator=(const punct &other){
x = other.x;
y = other.y;
return *this;
}
};
punct P1, P2;
struct comparex{
bool operator() (const punct &p1, const punct &p2){
return p1.x < p2.x;
}
};
struct comparey{
bool operator() (const punct &p1, const punct &p2){
return p1.y < p2.y;
}
};
double dist(const punct& p1, const punct &p2){
return sqrt( (p2.x - p1.x)*(p2.x - p1.x) + (p2.y - p1.y)*(p2.y - p1.y) );
}
double minimum_distance(vector<punct> X, vector<punct> Y, int st, int dr){
if(dr-st+1 == 2){
P1 = X[st]; P2 = X[dr];
return dist(X[st], X[dr]);
}
if(dr-st+1 == 3){
double d1, d2 ,d3;
d1 = dist(X[st], X[st+1]);
d2 = dist(X[st+1], X[dr]);
d3 = dist(X[st], X[dr]);
if(d1 <= d2 && d1 <= d3){
P1 = X[st]; P2 = X[st+1];
return d1;
}
if(d2 <= d1 && d2 <= d3){
P1 = X[st+1]; P2 = X[dr];
return d2;
}
if(d3 <= d1 && d3 <= d2){
P1 = X[st]; P2 = X[dr];
return d3;
}
}
if(dr-st+1 > 3){
int m = (st+dr) / 2;
double d = min(minimum_distance(X, Y, st, m), minimum_distance(X, Y, m+1, dr));
vector<punct> Y2;
// In Y2 retin punctele care sunt la o distanta mai mica sau egala cu d de dreapta (care coincide cu punctul din mijloc)
for(int i=st; i<=dr; i++)
if(dist(X[m], X[i]) <= d)
Y2.push_back(X[i]);
// Parcurg Y2 si compar d cu distanta dintre fiecare punct si urmatoarele 12 dupa el.
for(int i=0; i<Y2.size(); i++)
for(int j=1; j<=12; j++)
if(i+j<Y2.size()){
double d2 = dist(Y2[i], Y2[i+j]);
if(d2 < d){
d = d2;
P1 = Y2[i];
P2 = Y2[i+1];
}
}
return d;
}
}
int main()
{
int n, i;
vector<punct> V, X, Y;
f >> n;
for(i=0; i<n; i++){
int abscisa, ordonata;
f >> abscisa >> ordonata;
V.push_back(punct(abscisa, ordonata));
}
X = V;
Y = V;
sort(X.begin(), X.end(), comparex());
sort(Y.begin(), Y.end(), comparey());
minimum_distance(X, Y, 0, n-1);
g << dist(P1, P2);
f.close();
g.close();
return 0;
}