Cod sursa(job #2491840)

Utilizator aandreiAndrei Stanimir aandrei Data 13 noiembrie 2019 12:25:17
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

typedef struct Point
{
    int x, y;
} Point;
vector<Point> puncte;
double dist(Point p1, Point p2)
{
    return double((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
int operator<(Point& a, Point& b)
{
    return a.y<b.y;
}
double distanta_minima_banda(vector<Point> &banda, double delta)
{
    sort(banda.begin(),banda.end());
    double minim=delta;
    for (int i = 0; i < banda.size(); i++)
        for (int j = i+1; j < banda.size(); j++)
        {
            if(abs(banda[j].y-banda[i].y)>delta)
                break;
            else
                minim=min(minim,dist(banda[j],banda[i]));
        }
    return minim;
}


double distanta_minima(int st, int dr)
{
    if (dr - st == 1)
        return 9999999;
    if (dr - st == 2)
        return dist(puncte[st], puncte[st + 1]);
    if (dr - st == 3)
    {
        return min({dist(puncte[st], puncte[st + 1]),
                    dist(puncte[st], puncte[st + 2]),
                    dist(puncte[st + 1], puncte[st + 2])});
    }
    int mijloc=(dr+st)/2;
    double minim=min(distanta_minima(st,mijloc),distanta_minima(mijloc+1,dr));

    vector<Point> banda;
    for(int i=st;i<dr;i++){
        if(abs(puncte[i].x-puncte[mijloc].x)<minim)
            banda.push_back(puncte[i]);
    }
    return min(minim,distanta_minima_banda(banda,minim));
}

int main()
{
    const char iname[] = "cmap.in";
    const char oname[] = "cmap.out";
    int n;

    ifstream in(iname);
    ofstream out(oname);
    in >> n;
    puncte.resize(n);
    for (int i = 0; i < n; ++i)
    {
        Point p;
        in >> p.x >> p.y;
        puncte[i]=p;
    }

    in.close();
    out<<sqrt(distanta_minima(0,n));

}