Pagini recente » Cod sursa (job #1255306) | Cod sursa (job #206772) | Cod sursa (job #46979) | Cod sursa (job #1964974) | Cod sursa (job #2074281)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
#include <math.h>
using namespace std;
class Punct
{
public:
int x, y;
Punct()
{
x = y = 0;
}
Punct(int x, int y)
{
this->x = x;
this->y = y;
}
bool operator<(Punct const &other) const
{
return x < other.x;
}
double dist(Punct const &other) const
{
//cout << "dist=sqrt(" << ((long long) x - other.x) * (x - other.x) + ((long long)y - other.y) * (y - other.y) << ")\n";
return sqrt(((long long) x - other.x) * (x - other.x) + ((long long) y - other.y) * (y - other.y));
}
};
bool CompY (Punct const &a, Punct const &b)
{
return a.y < b.y;
}
vector<Punct> puncte, aux;
//left e inceputul, mid e mijloc + 1, right e sfarsitul + 1
//a si b sunt elementele cele mai apropiate
pair<Punct, Punct> DivImp(int left, int right)
{
if (right - left < 4) {
pair<Punct, Punct> closest = make_pair(puncte[left], puncte[right - 1]);
for (int i = left; i < right; ++i) {
for (int j = i + 1; j < right; ++j) {
if (puncte[i].dist(puncte[j]) < closest.first.dist(closest.second)) {
closest = make_pair(puncte[i], puncte[j]);
}
}
}
return closest;
} else {
int mid = (left + right + 1) / 2;
double dreapta = (puncte[mid - 1].x + puncte[mid].x) / 2;
pair<Punct, Punct> closest = DivImp(left, mid), closest2 = DivImp(mid, right);
if (closest.first.dist(closest.second) > closest2.first.dist(closest2.second)) {
closest = closest2;
}
double d = closest.first.dist(closest.second);
inplace_merge(puncte.begin() + left, puncte.begin() + mid, puncte.begin() + right, CompY);
vector<Punct> banda;
for (int i = left; i < right; ++i) {
if (dreapta - d <= puncte[i].x && puncte[i].x <= dreapta + d) {
banda.push_back(puncte[i]);
}
}
for (int i = 0; i < banda.size(); ++i) {
for (int j = i + 1; j < i + 8 && j < banda.size(); ++j) {
if (banda[i].dist(banda[j]) < d) {
d = banda[i].dist(banda[j]);
closest = make_pair(banda[i], banda[j]);
}
}
}
//cout << "dist " << d << "\n";
return closest;
}
}
int main()
{
fstream fin("cmap.in");
fstream fout("cmap.out");
int n;
Punct aux;
fin >> n;
puncte.resize(n);
for (int i = 0; i < n; ++i) {
fin >> aux.x >> aux.y;
puncte[i] = aux;
}
sort(puncte.begin(), puncte.end());
pair<Punct, Punct> closest = DivImp(0, n);
//cout << "(" << closest.first.x << "," << closest.first.y << "), (" << closest.second.x << "," << closest.second.y << ")\n";
//cout << "distanta: " << closest.first.dist(closest.second) << "\n";
fout << closest.first.dist(closest.second);
fin.close();
fout.close();
return 0;
}