Cod sursa(job #2065020)

Utilizator teo.cons98Constantin Teodor-Claudiu teo.cons98 Data 13 noiembrie 2017 11:20:12
Problema Cele mai apropiate puncte din plan Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 2.22 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<cmath>

using namespace std;

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

struct punct
{
    double x, y;
};

vector<punct> v, A;
unsigned int n;

double dist(punct A, punct B)
{
    return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

bool cmp(const punct A, const punct B)
{
    if(A.x < B.x)
    {
        return 1;
    }

    else if(A.x == B.x and A.y < B.y)
    {
        return 1;
    }

    return 0;
}

bool cmp2(const punct A, const punct B)
{
    if(A.y < B.y)
    {
        return 1;
    }

    else if(A.y == B.y and A.x < B.x)
    {
        return 1;
    }

    return 0;
}

void citire()
{
    fin >> n;
    v.resize(n);
    A.resize(n);
    for(int i = 0; i < n; ++i)
    {
        fin >> v[i].x >> v[i].y;
    }
}

double divide(unsigned int st, unsigned int dr)
{
    if(st == dr)
    {
        return 9999999;
    }
    else
    {
        unsigned int mid = (st + dr) / 2, st1, dr1;
        double dist1, dist2, d, midX, midY, minim;
        dist1 = divide(st, mid);
        dist2 = divide(mid + 1, dr);
        d = min(dist1, dist2);
        double e = d;

        midX = v[mid].x;

        st1 = mid;
        while(abs(v[st1].x - midX) <= d and st1 >= st)
        {
            --st1;
        }
        ++st1;

        dr1 = mid;
        while(abs(v[dr1].x - midX) <= d and dr1 < dr)
        {
            --dr1;
        }
        ++dr1;

        for(int i = st; i <= dr; ++i)
        {
            A[i] = v[i];
        }

        sort(A.begin() + st, A.begin() + mid, cmp2);
        sort(A.begin() + mid + 1, A.begin() + dr, cmp2);
        for(int i = st; i <= mid; ++i)
        {
            for(int j = mid + 1; j <= dr; ++j)
            {
                if(e > dist(A[i], A[j]))
                {
                    e = dist(A[i],A[j]);
                }
                else
                {
                    break;
                }
            }
        }

        return e;
    }
}

int main()
{
    citire();
    sort(v.begin(), v.end(), cmp);
    fout.precision(15);
    fout << divide(0, n - 1);
}