Cod sursa(job #2103787)

Utilizator AlexandraBalanBalan Alexandra AlexandraBalan Data 10 ianuarie 2018 20:07:01
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <limits.h>
#include <vector>
#include <math.h>
#include <cstdio>
#include <stdlib.h>
#include <iomanip>

using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct punct
{
    int x;
    int y;
};
vector <punct> v;
vector <punct> temp;

bool comp_x(punct a, punct b)
{
    return a.x<b.x;
}

bool comp_y(punct a, punct b)
{
    return a.y<b.y;
}

double dist2(punct a, punct b)
{
    double x=(double)(a.x-b.x);
    double y=(double)(a.y-b.y);
    return x*x+y*y;
}

double distanta (int prim, int ultim)
{   int i,j;
    if(ultim-prim==1)
        return dist2(v[prim],v[ultim]);
    if(ultim-prim==2)
        return min( dist2(v[prim], v[prim+1]), min ( dist2(v[prim+1],v[prim+2]), dist2(v[prim+2],v[prim] ) ) );
    int mij=(prim+ultim)/2;
    double d1=distanta(prim,mij);
    double d2=distanta(mij+1,ultim);
    double dist_min=min(d1,d2);
    for(i=prim;i<=ultim;i++)
    {
        if( (v[i].x-v[mij].x)*(v[i].x-v[mij].x) <=dist_min )
            temp.push_back(v[i]);
    }
    double d;
    sort(temp.begin(), temp.end(), comp_y);
    for(i=0;i<temp.size();i++)
        for(j=i+1;j<=i+7 && j<temp.size(); j++)
    {
        d=dist2(temp[i],temp[j]);
        dist_min=min(dist_min,d);
    }
    return dist_min;
}

int main()
{   int n;
    f>>n;
    punct p;
    int i;
    for(i=0;i<n;i++)
    {
        f>>p.x>>p.y;
        v.push_back(p);
    }
    sort(v.begin(),v.end(),comp_x);

    g<<fixed<<setprecision(6)<<sqrt(distanta(0,n-1));
    return 0;
}