Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Closest pair
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <cmath>
- #include <float.h>
- using namespace std;
- struct Punt {
- double x, y;
- };
- double min(double x, double y) {
- if (x < y) return x;
- return y;
- }
- bool comparadorX(const Punt& p1, const Punt& p2) {
- if (p1.x != p2.x) return p1.x < p2.x;
- return p1.y < p2.y;
- }
- bool comparadorY(const Punt& p1, const Punt& p2) {
- if (p1.y != p2.y) return p1.y < p2.y;
- return p1.x < p2.x;
- }
- double distancia(const Punt& p1, const Punt& p2) {
- return sqrt((p2.x - p1.x)*(p2.x - p1.x) +
- (p2.y - p1.y)*(p2.y - p1.y));
- }
- double distancia_min(const vector<Punt>& v, int n) {
- double dis;
- double min = DBL_MAX;
- for (int i = 0; i < n; ++i)
- for (int j = i+1; j < n; ++j) {
- dis = distancia(v[i], v[j]);
- if (dis < min) min = dis;
- }
- return min;
- }
- double propers_tira(const vector<Punt>& tira, int n, double d) {
- double dis;
- double min = d;
- for (int i = 0; i < n; ++i)
- for (int j = i+1; (j < n) and ((tira[j].y - tira[i].y) < min); ++j) {
- dis = distancia(tira[i], tira[j]);
- if (dis < min) min = dis;
- }
- return min;
- }
- double closest(vector<Punt> vx, vector<Punt> vy, int n) {
- if (n <= 3) return distancia_min(vx, n);
- int mig = n / 2;
- Punt puntMig = vx[mig];
- vector<Punt> vy_esquerra(mig+1);
- vector<Punt> vy_dreta(n-mig-1);
- int esq = 0, dre = 0;
- for (int i = 0; i < n; ++i) {
- if (vy[i].x <= puntMig.x) vy_esquerra[esq++] = vy[i];
- else vy_dreta[dre++] = vy[i];
- }
- double d_esq = closest(vx, vy_esquerra, mig);
- double d_dre = closest(vx, vy_dreta, n-mig);
- double d = min(d_esq, d_dre);
- vector<Punt> tira(n);
- int j = 0;
- for (int i = 0; i < n; ++i)
- if (abs(vy[i].x - puntMig.x) < d) {
- tira[j] = vy[i];
- j++;
- }
- return min(d, propers_tira(tira, j, d));
- }
- double closestPair(const vector<Punt>& v, int n) {
- vector<Punt> vx = v;
- vector<Punt> vy = v;
- sort(vx.begin(), vx.end(), comparadorX);
- sort(vy.begin(), vy.end(), comparadorY);
- return closest(vx, vy, n);
- }
- int main() {
- cout.setf(ios::fixed);
- cout.precision(5);
- double x, y;
- vector<Punt> v;
- while (cin >> x >> y)
- v.push_back({x, y});
- cout << closestPair(v, v.size()) << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement