Cod sursa(job #2074018)

Utilizator djmafy2000Andrei djmafy2000 Data 23 noiembrie 2017 23:18:08
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.12 kb
#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> V, vector<punct> X, vector<punct> Y, int st, int dr){
    if(dr-st+1 == 2){
        P1 = V[st]; P2 = V[dr];
        return dist(V[st], V[dr]);
    }

    if(dr-st+1 == 3){
        double d1, d2 ,d3;
        d1 = dist(V[st], V[st+1]);
        d2 = dist(V[st+1], V[dr]);
        d3 = dist(V[st], V[dr]);
        if(d1 <= d2 && d1 <= d3){
            P1 = V[st]; P2 = V[st+1];
            return d1;
        }
        if(d2 <= d1 && d2 <= d3){
            P1 = V[st+1]; P2 = V[dr];
            return d2;
        }
        if(d3 <= d1 && d3 <= d2){
            P1 = V[st]; P2 = V[dr];
            return d3;
        }
    }
    if(dr-st+1 > 3){
        int m = (st+dr) / 2;
        double d = min(minimum_distance(V, X, Y, st, m), minimum_distance(V, 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(V[m], V[i]) <= d)
                Y2.push_back(V[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(V, X, Y, 0, n-1);
    g << dist(P1, P2);

    f.close();
    g.close();
    return 0;
}