Cod sursa(job #1765449)

Utilizator tqmiSzasz Tamas tqmi Data 26 septembrie 2016 19:05:46
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define oo 1000000005
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int N;
double sol;
pair <int,int>puncte[100005];
void read()
{
    fin>>N;
    for(int i=1;i<=N;i++)
    {
        fin>>puncte[i].first>>puncte[i].second;
    }
    sort(puncte+1,puncte+1+N);
}
double dist(pair <int,int>A,pair<int, int > B)
{
    return sqrt(1LL*(A.first-B.first)*(A.first-B.first)+1LL*(A.second-B.second)*(A.second-B.second));
}
bool comp(pair<int,int>A,pair<int,int>B)
{
    return A.second>B.second;
}
double DEI(int left,int right)
{
    double S=oo,S1=oo,S2=oo;
    if(right-left > 3)
    {
        int mid=(left+right)/2;
        S1=DEI(left,mid);
        S2=DEI(mid+1,right);
        S=min(S1,S2);
    }
    else
    {
        for(int i=left;i<right;i++)
        {
            for( int j=i+1;j<=right;j++)
            {
                S=min(S,dist(puncte[i],puncte[j]));
            }
        }
        return S;
    }
    int mid=(left+right)/2;
    int middle = (puncte[mid].first+puncte[mid+1].first)/2;
    pair <int,int> Y[50];
    int k=0;
    for(int i=left;i<=right;i++)
    {
        if(abs(puncte[i].first-middle)<=S)
        {
            Y[++k]=puncte[i];
        }
    }
    sort(Y+1,Y+k+1,comp);
    for(int i=1;i<=k;i++)
    {
        for(int j=i+1;j<=k;j++)
        {
            S=min(S,dist(puncte[i],puncte[j]));
        }
    }
    return S;
}
void solve()
{
    sol=DEI(1,N);
}
void print()
{
    fout<<fixed<<setprecision(6)<<sol<<"\n";
}
int main()
{
    read();
    solve();
    print();
}