Cod sursa(job #2068369)

Utilizator RSorinRadu Sorin Gabriel RSorin Data 17 noiembrie 2017 18:06:55
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <cmath>
#include <stdlib.h>
#include <algorithm>
#include <iomanip>
#include <float.h>
using namespace std;
ifstream fin;
ofstream fout;
struct punct
{
    int x,y;
};
bool comp1(punct a,punct b)
{
    return (a.x < b.x);
}
bool comp2(punct a,punct b)
{
    return (a.y < b.y);
}
double d(punct a,punct b)
{
     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double Distanta(vector<punct> v,vector<punct> w,int st,int dr)
{
    if (dr-st == 1)
        return d(v[st],v[dr]);
    if (dr-st == 2)
        return min(min(d(v[st],v[st+1]),d(v[st+1],v[dr])),d(v[st],v[dr]));
    double dist;
    int m = (st+dr)/2;
    double d1 = Distanta(v,w,st,m);
    double d2 = Distanta(v,w,m+1,dr);
    dist = min(d1,d2);
    vector <punct> aux;
    for (int i=st;i<dr;i++)
         if (abs(w[i].x - w[m].x) < dist)
            aux.push_back(w[i]);
    double d3 = DBL_MAX;
    for (int i=0;i<aux.size();i++)
    {
        int j = i+1;
        while ((j <= i+7) && (j < aux.size()))
        {
              d3 = min(d3,d(w[i],w[j]));
              j++;
        }
    }
    dist = min(dist,d3);
    return dist;
}
int main()
{
    vector <punct> punctex,punctey;
    fin.open("cmap.in");
    int n;
    fin >> n;
    for(int i=0;i<n;i++)
    {
        punct a;
        fin >> a.x >> a.y;
        punctex.push_back(a);
    }
    fin.close();
    punctey = punctex;
    sort(punctex.begin(),punctex.end(),comp1);
    sort(punctey.begin(),punctey.end(),comp2);
    fout.open("cmap.out");
    fout << fixed << setprecision(6) << Distanta(punctex,punctey,0,n-1);
    fout.close();
    return 0;
}