Cod sursa(job #1615624)

Utilizator sergiunascaSergiu Nasca sergiunasca Data 26 februarie 2016 18:36:35
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
//
//  main.cpp
//  Puncte
//
//  Created by Nasca Sergiu Alin on 24/02/16.
//  Copyright © 2016 Nasca Sergiu Alin. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>

float distance = 1<<30;

typedef struct punct
{
    int x;
    int y;
}punct;

bool cmpX(punct A,punct B)
{
    return A.x < B.x;
}

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

std::vector<punct> format(std::vector<punct> a, int start, int stop)
{
    std::vector<punct> b;
    b.assign(a.begin()+start, a.begin()+stop);
    return b;
}

float divide(std::vector<punct> a)
{
    int mij = int(a.size()/2);
    if(a.size() == 1)
    {
        return  distanceAB(a[0], a[1]);
    }
    else if(a.size() == 2)
    {
        return std::min(std::min(distanceAB(a[0], a[1]), distanceAB(a[1], a[2])), distanceAB(a[0], a[2]));
    }
    else
    {
        distance = std::min(distance, divide( format(a,0,mij) ));
        distance = std::min(distance, divide( format(a,mij+1,int(a.size())) ));
        //distance = std::min(distance, );
    }
    
    return distance;
}

int main()
{
    int n;
    punct local;
    std::vector<punct> a;
    freopen("cmap.in", "r", stdin);
    freopen("cmap.out", "w", stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d %d",&local.x,&local.y);
        a.push_back(local);
    }
    std::sort(a.begin(), a.end(), cmpX);
    /*for(int i=0;i<a.size();++i)
    {
        printf("%d\n",a[i].x);
    }*/
    printf("%f",divide(a));
    return 0;
}