Cod sursa(job #1026294)

Utilizator vladm97Matei Vlad vladm97 Data 11 noiembrie 2013 14:39:24
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.44 kb
#include <cstdio>
#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;

int n;

struct punct
{
    long long x;
    long long y;
}v[100010];
vector <punct> vec;
bool sortY(const punct &a, const punct &b)
{
    return (a.y < b.y);
}

bool sortX(const punct &a,const punct &b)
{
    return (a.x < b.x);
}

double myDistance(const punct &a1, const punct &a2)
{
    double d = (double) (a1.x - a2.x) * (a1.x - a2.x) + (a1.y - a2.y) * (a1.y - a2.y) ;
    d = sqrt(d);
    return d;
}




double devideAndConquer(const int &left,const int &right)
{
    double d;
    if(right - left <= 2)
    {
        d = 1000000000.0;

        for(int i = left; i < right ; i++ )
        {
            for(int j = i + 1 ; j<= right; j++)
            {
                d = min(myDistance(v[i], v[j]),d);
            }
        }
        sort(v+left, v + right + 1, sortY);
        return d;
    }
    else
    {
        int middle = left + (right - left) / 2;

        d = min(devideAndConquer(left, middle),devideAndConquer(middle + 1, right));

        int l = left;
        int r = middle+1;

        vec.clear();
        while( (l <= middle) && (r <= right) )
        {
            if( sortY(v[l], v[r]) == true)
            {
                vec.push_back(v[l]);
                l++;
            }
            else
            {
                vec.push_back(v[r]);
                r++;
            }
        }

        while( l <= middle )
        {
            vec.push_back(v[l]);
            l++;
        }

        while( r <= right )
        {
            vec.push_back(v[r]);
            r++;
        }

        for(int i = left, k = 0; i<=right; i++,k++)
        {
            v[i] = vec[k];
        }

        for(int i = left ; i<= right ; i++)
        {
            for(int j = i+1; (j <= right) && (j-i < 7) ; j++)
            {
                d = min(myDistance(v[i],v[j]),d);
            }
        }

        return d;
    }
}

void read()
{
    freopen("cmap.in", "r", stdin);
    scanf("%d", &n);
    for (int i = 0; i <n ; ++i)
    {
        scanf("%lld %lld", &(v[i].x), &(v[i].y));
    }
}

void write(const double &d)
{
    FILE*g = fopen("cmap.out","w");
    fprintf(g, "%.6lf\n", d);
}
int main()
{
    read();
    sort(v ,v + n , sortX );
    double d = devideAndConquer(0,n-1);
    write(d);
}