Cod sursa(job #1076227)

Utilizator Aida_SilviaStrimbeanu Aida Silvia Aida_Silvia Data 9 ianuarie 2014 23:12:27
Problema Cele mai apropiate puncte din plan Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 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)
{
    if (a.x>b.x) return false;
    else if (a.x<b.x) return true;
    else if (a.x==b.x) return a.y<b.y;
}


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((a.x-b.x) * 1.0 *(a.x-b.x)+(a.y-b.y)* 1.0 *(a.y-b.y));
}

double solve(int start, int finish)
{
    if (finish-start<=3)
    {

        double dist= 1.0 * (1 << 20);
        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;
}