Cod sursa(job #2103849)

Utilizator AlexandraBalanBalan Alexandra AlexandraBalan Data 10 ianuarie 2018 20:53:45
Problema Cele mai apropiate puncte din plan Scor 85
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 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;


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

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

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

long long distanta (int prim, int ultim)
{
    int i,j;
    vector <punct> temp;
    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;

    long long d1=distanta(prim,mij);
    long long d2=distanta(mij+1,ultim);
    long long 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]);
    }

    long long 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);

    /*for(i=0; i<v.size(); i++)
        cout<<v[i].x<<" "<<v[i].y<<endl;*/


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