Cod sursa(job #2134318)

Utilizator sandu.m.mdMorari Sandu sandu.m.md Data 17 februarie 2018 20:33:38
Problema Cele mai apropiate puncte din plan Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 2.59 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
//#include "grafic.h"
#include <limits>
#include <set>
#include <math.h>
#include <iomanip>

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

struct pair_double{
    double first, second;
};

vector<pair_double> vec;
int n;
double x, y, a;

double dist(pair_double a, pair_double b){
    return sqrt(pow(a.first - b.first, 2) + pow(a.second - b.second, 2));
}

bool cmp(pair_double a, pair_double b){
    bool ch = false;
    if(a.first < b.first)
        ch = true;
    else if(a.first == b.first && a.second < b.second)
        ch = true;
    return ch;
}


int left_poz(int mid, double value)
{
    int i = mid;
    while(i >= 0 && vec[i].first >= value)
    {
        i--;
    }
    return ++i;
}

int right_poz(int mid, double value)
{
    int i = mid + 1;
    while(i < n && vec[i].first <= value)
    {
        i++;
    }
    return --i;
}

double MinDist(int mid, double value1, double value2)
{
    int left = left_poz(mid, value1);
    int right = right_poz(mid, value2);
    double minim = numeric_limits<double>::max(), current;
    for(int i = left; i <= mid; i++){
        for(int j = mid + 1; j <= right; j++){
            current = dist(vec[i], vec[j]);
            if(minim > current)
                minim = current;
        }
    }
    return minim;
}

double res(int start, int stop)
{
    if (stop - start + 1 <= 3)
    {
        double minim = numeric_limits<double>::max();
        for (int i = start; i < stop; i++)
        {
            a = dist(vec[i], vec[i + 1]);
            if (minim > a)
                minim = a;
        }
        return minim;
    } 
    else if(stop - start + 1 > 3)
    {
        int mid = start + (stop - start) / 2;
        double drept = vec[mid].first + (vec[mid + 1].first - vec[mid].first) / 2;
        double minim = min(res(start, mid), res(mid + 1, stop));
        double current = MinDist(mid, drept - minim, drept + minim);
        if(minim > current)
            minim = current;
        return minim;
    }
}

int main()
{

    fin >> n;
    pair_double aux;
    for (int i = 0; i < n; i++)
    {
        fin >> aux.first >> aux.second;
        vec.push_back(aux);
    }


    sort(vec.begin(), vec.end(), cmp);
    //cout << "rs: " << right_poz(5, 92) << "\n";
    
    fout << setprecision(8) << res(0, n - 1) << "\n";
/*
    for(int i = 0; i < n; i++){
        cout << vec[i].first << " " << vec[i].second << "\n";
    }
*/
    return 0;
}