Cod sursa(job #1076244)

Utilizator Aida_SilviaStrimbeanu Aida Silvia Aida_Silvia Data 9 ianuarie 2014 23:25:46
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iomanip>

#define x first
#define y second

using namespace std;

int n;
pair <int, int> Puncte[100073];

bool cmp(const pair<int, int>& a,const pair<int, int>& b)
{
    return a.x < b.x;
}


bool cmp2(const pair<int, int>& a,const pair<int, int>& b)
{
    return a.y<b.y;
}

double distanta(const pair<int, int>& a,const pair<int, int>& b)
{
    return sqrt(1LL * (a.x-b.x) * (a.x-b.x)+1LL * (a.y-b.y)* (a.y-b.y));
}

double solve(int start, int finish)
{
    if (finish-start<=3)
    {
        double dist= (1 << 31) - 1;
        for (int i=start; i<=finish; i++)
            for (int j=start; j<=finish; j++)
                if(i!=j) dist=min(dist,distanta(Puncte[i],Puncte[j]));
        return dist;

    }
    else
    {
        int mijloc=(start+finish)/2;
        double d1=solve(start,mijloc);
        double d2=solve(mijloc+1,finish);

        double d=min(d1,d2);

        vector<pair<int, int> > aux;

        for (int i=start; i<=mijloc; i++)
            if (Puncte[mijloc].x-Puncte[i].x<=d) aux.push_back(Puncte[i]);
        for (int i=mijloc+1; i<=finish; i++)
            if (Puncte[i].x-Puncte[mijloc].x<=d) aux.push_back(Puncte[i]);

        sort(aux.begin(),aux.end(),cmp2);

        for (int i=0; i<aux.size(); i++)
            for (int j=1; j<8 && i+j<aux.size(); j++)
                d=min(d, distanta(Puncte[i],Puncte[i+j]));

        return d;

    }

}

int main()
{
    ifstream in("cmap.in");
    ofstream out("cmap.out");

    in>>n;

    for (int i=0; i<n; i++)
    {
        in>>Puncte[i].x>>Puncte[i].y;
    }

    sort(Puncte,Puncte+n,cmp);
    out<<setprecision(20)<<solve(0,n-1);


    return 0;
}