Cod sursa(job #1615695)

Utilizator sergiunascaSergiu Nasca sergiunasca Data 26 februarie 2016 19:30:02
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.29 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;
}

bool cmpY(punct A,punct B)
{
    return A.y < B.y;
}

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

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 line(std::vector<punct> a)
{
    float local = 1<<30;
    
    std::sort(a.begin(), a.end(), cmpY);
    
    for(int i=0;i<a.size();++i)
    {
        //printf("\n\nA: %d %d\n",a[i].x,a[i].y);
        for(int j=i+1;j<a.size();++j)
        {
            if(abs(a[i].y - a[j].y) > distance)break;
            else local = std::min(local, distanceAB(a[i], a[j]));
        }
    }
    //printf("local: %f\n",local);
    return local;
}

float divide(std::vector<punct> a)
{
    int mij = int((a.size()-1)/2);
    if(a.size() == 2)
    {
        return  distanceAB(a[0], a[1]);
    }
    else if(a.size() == 3)
    {
        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+1) ));
        distance = std::min(distance, divide( format(a,mij+1,int(a.size())) ));
        int start,stop;
        for(start = mij; std::abs(a[mij].x - a[start].x) < distance && start >= 1; start--);
        for(stop = mij; std::abs(a[mij].x - a[stop].x) < distance  && stop < a.size(); stop++);
        distance = std::min(distance, line( format(a, start, stop) ));
    }
    
    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;
}