Cod sursa(job #1909909)

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

ifstream f("cmap.in");
ofstream g("cmap.out");
int n;
double u = inf,mn;
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)
{
    if(a==b)
        g<<"NU";
    return sqrt(((double)(a.first-b.first) * (a.first-b.first)) + ((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;
}
int X;
vector<pair<int,int> > A,B;

double divide(int a,int b)
{
    if (b-a+1<=1)
        return inf;

    double mn = min(divide(a,(a+b)/2),divide((a+b)/2+1,b));

    A.clear();
    B.clear();

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

   /* for (int i=0;i<A.size();i++)
        g<<A[i].first<<' '<<A[i].second<<' ';
    g<<'\n';
    for (int i=0;i<B.size();i++)
        g<<B[i].first<<' '<<B[i].second<<' ';

    g<<'\n'<<'\n';*/

    int i1 = 0,i2 = 0;
    while (i1<A.size() && i2<B.size())
    {

        for(int i3 = min(0,i2 - 4) ;i3 < min((int)B.size(), i2+5);i3++)
            mn = min(mn,dist(A[i1],B[i3]));
       /*
        if (i2>3)
            mn = min(mn,dist(A[i1],B[i2-4]));
        if (i2>2)
            mn = min(mn,dist(A[i1],B[i2-3]));
        if (i2>1)
            mn = min(mn,dist(A[i1],B[i2-2]));
        if (i2>0)
            mn = min(mn,dist(A[i1],B[i2-1]));

        //g<<mn<<'\n';


        if (i2<B.size()-1)
            mn = min(mn,dist(A[i1],B[i2+1]));
        if (i2<B.size()-2)
            mn = min(mn,dist(A[i1],B[i2+2]));
        if (i2<B.size()-3)
            mn = min(mn,dist(A[i1],B[i2+3]));
        if (i2<B.size()-4)
            mn = min(mn,dist(A[i1],B[i2+4]));

      //  g<<mn<< ' '<<i1<<' '<<i2<<'\n';
*/
        if (A[i1].second<B[i2].second)
            i1++;
        else
            i2++;
    }


    A.clear();
    B.clear();

    return mn;
}

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

     double x = divide(1,n);

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

    return 0;
}