Cod sursa(job #2071768)

Utilizator mamamea132Pronoza Cristian-Valentin mamamea132 Data 20 noiembrie 2017 23:14:58
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.47 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
struct punct{
    int x,y;
};
void citire(vector<punct> &puncte)
{
    ifstream in("cmap.in");
    int nr;
    in>>nr;
    punct dummy;
    while(in>>dummy.x>>dummy.y)
        puncte.push_back(dummy);
    in.close();
}
float distanta(punct A,punct B)
{
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
int comparator(punct A,punct B)
{
    return A.x<B.x;
}
int comparatorY(punct A,punct B)
{
    return A.y<B.y;
}

void distantaMerged(int left, int m, int right, vector<punct> &puncte, punct mijloc, float &disMin)
{
    vector<punct> aux;
    vector<punct> bandaDistMin;
    int iL=left;
    int iR=m+1;
    int nrElementeL=m-left+1;
    int nrElementeR=right-m;
    while(nrElementeR&&nrElementeL)
    {
        if(puncte[iL].y<puncte[iR].y)
        {
            if(abs(mijloc.x-puncte[iL].x)<disMin)  bandaDistMin.push_back(puncte[iL]);
            aux.push_back(puncte[iL]);
            iL++;
            nrElementeL--;
        }
        else
        {
            if(abs(mijloc.x-puncte[iR].x)<disMin)  bandaDistMin.push_back(puncte[iR]);
            aux.push_back(puncte[iR]);
            iR++;
            nrElementeR--;
        }
    }
    if(nrElementeR)
    {
        while(nrElementeR)
        {
            if(abs(mijloc.x-puncte[iR].x)<disMin) bandaDistMin.push_back(puncte[iR]);
            aux.push_back(puncte[iR]);
            iR++;
            nrElementeR--;
        }
    }
    else
    {
        while(nrElementeL)
        {
            if(abs(mijloc.x-puncte[iL].x)<disMin)  bandaDistMin.push_back(puncte[iL]);
            aux.push_back(puncte[iL]);
            iL++;
            nrElementeL--;
        }
    }
    for(int i=left;i<=right;i++)
    {
        puncte[i]=aux[i-left];
    }
    for(int i=0;i<bandaDistMin.size()-1;i++)
    {
        for(int j=i+1;j<bandaDistMin.size()&&j<i+8;j++)
        {
            float d=distanta(bandaDistMin[i],bandaDistMin[j]);
            if(d<disMin&&d!=0)
            {
                disMin=d;
            }
        }
    }
}
float distantaMinima(int left,int right,vector<punct> &puncte)
{
    if(right-left==1)
    {
        if(puncte[left].y>puncte[right].y)
        {
            punct aux=puncte[left];
            puncte[left]=puncte[right];
            puncte[right]=aux;
        }
        return distanta(puncte[left],puncte[right]);
    }
    else
        if(right-left==2)
        {
            sort(puncte.begin()+left,puncte.begin()+right,comparatorY); //3 elemente
            float d1=distanta(puncte[left],puncte[left+1]);
            float d2=distanta(puncte[left+1],puncte[right]);
            float d3=distanta(puncte[left], puncte[right]);
            if(d1<=d2&&d1<=d3)  return d1;
            if(d2<=d1&&d2<=d3)  return d2;
            if(d3<=d2&&d3<=d1)  return d3;
        }
        else
        {
            int m=(left+right)/2;
            punct mijloc=puncte[m];
            float x=min(distantaMinima(left,m,puncte),distantaMinima(m+1,right,puncte));
            distantaMerged(left,m,right,puncte,mijloc,x);
            return x;
        }
}
int main()
{
    vector<punct> puncte;
    citire(puncte);
    sort(puncte.begin(),puncte.end(),comparator);
    float result=distantaMinima(0,puncte.size()-1,puncte);
    ofstream out("cmap.out");
    out<<result;
    out.close();
    return 0;
}