Cod sursa(job #1027028)

Utilizator maritimCristian Lambru maritim Data 12 noiembrie 2013 13:02:23
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;

ifstream f("cmap.in");
FILE *g = fopen("cmap.out","w");

typedef struct Compare
{
    bool operator() (const pair<int,int> a,const pair<int,int> b) 
    {
        if(a.second == b.second)
            return a.first < b.first;
        return a.second < b.second;
    }
} ICompare;

#define MaxN 100100
#define mid ((li+ls)>>1)
#define pint pair<double,double>

int N;
double Sol;
vector<pair<double,double> > A;
vector<pair<double,double> > Y;

void citire(void)
{
    int x,y;

    f >> N;

    for(int i=1;i<=N;i++)
    {
        f >> x >> y;
        A.push_back(make_pair(x,y));
    }
}

inline double dist(pint a,pint b)
{
    return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}

inline double getDist(pint a,pint b,pint c)
{
    return min(dist(a,b),min(dist(a,c),dist(b,c)));
}

inline double DEI(int li,int ls)
{
    if(ls-li == 1)
        return dist(A[li],A[ls]);
    else if(ls-li == 2)
        return getDist(A[li],A[li+1],A[ls]);

    double dis = DEI(li,mid);
    dis = min(dis,DEI(mid+1,ls));

    Y.clear();

    for(int i=mid;i>=li && A[mid].first-A[i].first <= dis;i--)
        Y.push_back(A[i]);
    for(int i=mid+1;i <= ls && A[i].first-A[mid].first <= dis;i++)
        Y.push_back(A[i]);

    sort(Y.begin(),Y.end(),ICompare());

    for(int i=0;i<Y.size();i++)
        for(int j=i+1;j<Y.size() && j<i+8;j++)
            dis = min(dis,dist(Y[i],Y[j]));

    return dis;
}

void Rezolvare(void)
{
    sort(A.begin(),A.end());

    Sol = DEI(0,N-1);
}

int main()
{
    citire();
    Rezolvare();

    fprintf(g,"%.6lf\n",Sol);
}