Cod sursa(job #1909477)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 7 martie 2017 12:51:50
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.29 kb
#include <fstream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <algorithm>
#define Nmax 100001
#define inf 1e9
using namespace std;

ifstream f("cmap.in");
ofstream g("cmap.out");

int n;
double u = inf;
pair<int,int> v[Nmax];

bool comp(pair<int,int> a, pair<int,int> b)
{
    return a.first<b.first;
}

double dist(pair<int,int> a, pair<int,int> b)
{
    return sqrt(((long double)(a.first-b.first) * (a.first-b.first)) + ((long double)(a.second-b.second) * (a.second-b.second)));
}

int ctbU(int x,int st,int dr)
{
    int mij;
    while (st<=dr)
    {
        int mij = (st+dr)/2;
        if (v[mij].first>=x)
            dr = mij-1;
        else
            st = mij+1;
    }
    return st;
}
int ctbD(int x,int st,int dr)
{
    int mij;
    while (st<=dr)
    {
        int mij = (st+dr)/2;
        if (v[mij].first>x)
            dr = mij-1;
        else
            st = mij+1;
    }
    return dr;
}

bool comp2(pair<int,int> a,pair<int,int> b)
{
    return a.second<b.second;
}

double divide(int a,int b)
{
    if (b-a+1==1)
    {
        return inf;
    }
    double u1 = divide(a,(a+b)/2);
    double u2 = divide((a+b)/2+1,b);
    u = min(u,min(u1,u2));
    vector<pair<int,int> > A,B;

    for (int i=(a+b)/2;v[i].first>=v[(a+b)/2].first - u && i>=a;i--)
        A.push_back(v[i]);
    sort(A.begin(),A.end(),comp2);

    for (int i=(a+b)/2+1;v[i].first<=v[(a+b)/2+1].first + u && i<=b;i++)
        B.push_back(v[i]);
    sort(B.begin(),B.end(),comp2);

    int i1 = 0,i2 = 0;
    while (i1<A.size() && i2<B.size())
    {
        if (i2>1)
            u = min(u,dist(A[i1],B[i2-2]));
        if (i2>0)
            u = min(u,dist(A[i1],B[i2-1]));
        u = min(u,dist(A[i1],B[i2]));
        if (i2<B.size()-1)
            u = min(u,dist(A[i1],B[i2+1]));
        if (i2<B.size()-2)
            u = min(u,dist(A[i1],B[i2+2]));
        if (A[i1].second<B[i2].second)
            i1++;
        else
            i2++;
    }
    A.clear();
    B.clear();
    return u;
}

int main()
{
    f>>n;
    for (int i=1;i<=n;i++)
    {
        int x,y;
        f>>x>>y;
        v[i] = make_pair(x,y);
    }

    sort(v+1,v+n+1,comp);

    divide(1,n);

    g<<fixed;
    g<<setprecision(7)<<u;

    return 0;
}