Cod sursa(job #2280446)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 10 noiembrie 2018 17:10:51
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.23 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>

#define x first
#define y second

using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

const int NMax = 100005;
pair < int, int > Puncte[NMax];
int nr_Puncte;

void Read()
{
    fin >> nr_Puncte;

    for(int i = 1; i <= nr_Puncte; ++i)
    {
        fin >> Puncte[i].x >> Puncte[i].y;
    }
}

void Print(pair <int, int > vec[], int nr)
{
    for(int i = 1; i <= nr; ++i)
    {
        fout << vec[i].x << " " << vec[i].y << "\n";
    }

    fout << "\n";
    fout << "\n";
    fout << "\n";
}

double Calc_Dist(pair < int, int > p1, pair < int, int > p2)
{
    return ((double)p1.x - p2.x) * (p1.x - p2.x) + (1.0 * p1.y - p2.y) * (p1.y - p2.y);
}

double mindist = 1.0 * 0x3f3f3f3f;

int modul(int x)
{
    if(x < 0)
        return -x;
    return x;
}

struct MyClass {
    bool operator() (pair < int, int > p1, pair < int, int > p2)
    {
        return p1.y < p2.y;
    }
} Compare;

pair < int, int > strip[NMax];

double DivideEtImpera(int st, int dr)
{
    if (dr - st == 1)
    {
        return Calc_Dist(Puncte[st], Puncte[dr]);
    }

    else if(dr - st == 2)
    {
        double dist1 = Calc_Dist(Puncte[st], Puncte[st+1]);
        dist1 = min(dist1, Calc_Dist(Puncte[st+1], Puncte[dr]));
        dist1 = min(dist1, Calc_Dist(Puncte[st], Puncte[dr]));
        return dist1;
    }

    int mij = (st + dr) / 2;
    int xmin = Puncte[mij].x;

    double d1 = DivideEtImpera(st, mij);
    double d2 = DivideEtImpera(mij+1, dr);

    d1 = min(d1, d2);
    int k = 0;

    for(int i = st; i <= dr; ++i)
        if(modul(xmin - Puncte[i].x) < d1)
            strip[++k] = Puncte[i];

    sort(strip + 1, strip + k + 1, Compare);

    for(int i=1; i <= k; ++i)
        for(int j = 1; j <= 8; ++j)
            if( i + j <= k)
            {
                double dist = Calc_Dist(Puncte[i], Puncte[i + j]);
                d1 = min(dist, d1);
            }

    return d1;
}

int main()
{
    Read();

    sort(Puncte + 1, Puncte + nr_Puncte + 1);

    fout << fixed << setprecision(6) << sqrt(DivideEtImpera(1, nr_Puncte));

    return 0;
}