Pagini recente » Cod sursa (job #931318) | Cod sursa (job #220021) | Cod sursa (job #2907013) | Cod sursa (job #1906433) | Cod sursa (job #2072594)
#include <iostream>
#include <vector>
#include <cmath>
#include <cfloat>
#include <unordered_map>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <sstream>
using namespace std;
struct point {
long long x;
long long y;
point(long long x, long long y) : x(x), y(y) {}
string toString() {
stringstream ss;
ss << "(x: "<<x<<", y: "<<y<<")";
return ss.str();
}
};
double distance(point* p1, point* p2) {
long long f1 = (p1->x - p2->x) * (p1->x - p2->x);
long long f2 = (p1->y - p2->y) * (p1->y - p2->y);
return sqrt(f1 + f2);
}
double naive(vector<point*> pts) {
if (pts.empty()) return DBL_MAX;
if (pts.size() ==1) return DBL_MAX;
auto min_dist = DBL_MAX;
for (int i = 0; i < pts.size() - 1; i++) {
for (int j = i + 1; j < pts.size(); j++) {
double dd = distance(pts[i], pts[j]);
if (dd < min_dist)
min_dist = dd;
}
}
return min_dist;
}
double min_strip_distance(vector<point*> strip, double dist) {
auto min_dist = DBL_MAX;
for (int i = 0; i < strip.size(); i++) {
for (int j = i + 1; j < strip.size() && (strip[j]->y - strip[i]->y <= dist); j++) {
double dd = distance(strip[i], strip[j]);
if (dd < min_dist) {
min_dist = dd;
}
}
}
return min_dist;
}
double compute(vector<point*> px, vector<point*> py) {
if (px.size() <= 3)
return naive(px);
point* mid_point = px[px.size() / 2];
vector<point*> pxL, pxR;
unordered_map<point*, int> mapSides;
int side = 1;
for (auto p : px) {
if (p->x < mid_point->x) {
pxL.push_back(p);
mapSides[p] = -1;
} else if (p->x == mid_point->x) {
if (side == -1) {
pxL.push_back(p);
} else {
pxR.push_back(p);
}
mapSides[p] = side;
side *= -1;
} else {
pxR.push_back(p);
mapSides[p] = 1;
}
}
vector<point*> pyL, pyR;
for (auto p : py) {
if (mapSides[p] == -1) {
pyL.push_back(p);
} else {
pyR.push_back(p);
}
}
double distL = compute(pxL, pyL);
double distR = compute(pxR, pyR);
double d = min(distL, distR);
vector<point*> strip;
for (auto p : py) {
if (abs(p->x - mid_point->x) <= d) {
strip.push_back(p);
}
}
return min(d, min_strip_distance(strip, d));
}
double closest(vector<point*> points) {
vector<point*> px, py;
for (auto p : points){
px.push_back(p);
py.push_back(p);
}
sort(px.begin(), px.end(), [](point* p1, point* p2) -> bool { return p1->x < p2->x; });
sort(py.begin(), py.end(), [](point* p1, point* p2) -> bool { return p1->y < p2->y; });
return compute(px, py);
}
vector<point*> read(istream &fin) {
vector<point*> points;
int n;
fin>>n;
while (n) {
long long x, y;
fin>>x>>y;
points.push_back(new point(x, y));
n--;
}
return points;
}
int main() {
ifstream fin("cmap.in");
ofstream fout("cmap.out");
vector<point*> pts = read(fin);
// cout<<fixed<<distance(pts[0], pts[1]);
// for (auto p : pts) cout<<p->toString()<<endl;
double d = closest(pts);
fout<<fixed<<setprecision(6)<<d<<endl;
fin.close();
fout.close();
return 0;
}