Cod sursa(job #2496629)

Utilizator aandreiAndrei Stanimir aandrei Data 21 noiembrie 2019 11:05:14
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.75 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;

typedef struct Point
{
    int x, y;
} Point;
vector<Point> puncte;
vector<Point> puncteY;
double dist(Point p1, Point p2)
{
    return sqrt(double((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)));
}
/*
bool compareY(Point& a, Point& b)
{
    return a.y-b.y;
}
bool compareX(Point a, Point b)
{
    if(a.x==b.x)
        return a.y-b.y;
    return a.x-b.x;
}*/
struct {
        bool operator()(Point a, Point b) const
        {
            if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
        }
    } compareX;
struct {
        bool operator()(Point a, Point b) const
        {
    return a.y<b.y;
        }
    } compareY;

double distanta_minima_banda(vector<Point> &banda, double delta)
{
    sort(banda.begin(),banda.end(),compareY);
    /*for(auto p : banda)
    {
        cout<<p.x<<" "<<p.y<<"\n";
    }
    cout<<endl;
    */
    for (int i = 0; i < banda.size(); i++)
        for (int j = i+1; j < banda.size(); j++)
        {
            if(banda[j].y-banda[i].y>=delta)
                break;
            else
                delta=min(delta,dist(banda[j],banda[i]));
        }
    return delta;
}


double distanta_minima(int st, int dr)
{
    if (dr - st == 0)
        return 9999999;
    if (dr - st == 1)
        return dist(puncte[st], puncte[st + 1]);
    if (dr - st == 2)
    {
        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;

    //for punteY ===> puncteYS  puncteYD

    double minim=min(distanta_minima(st,mijloc),distanta_minima(mijloc+1,dr));

    vector<Point> banda;

    //for in punctey
    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);
    puncteY.resize(n);
    for (int i = 0; i < n; ++i)
    {
        Point p;
        in >> p.x >> p.y;
        puncte[i]=p;
        puncteY[i]=p;
    }

    in.close();
    sort(puncte.begin(),puncte.end(),compareX);
    sort(puncteY.begin(),puncteY.end(),compareY);
    //sort dupa y puncteY
    /*
    for(auto p : puncte)
    {
        cout<<p.x<<" "<<p.y<<"\n";
    }
    cout<<endl;
    */

    //apel (0,n-1, puncteY)
    out<<setprecision(20)<<distanta_minima(0,n-1);
    out.close();
}