Cod sursa(job #1026197)

Utilizator vladm97Matei Vlad vladm97 Data 11 noiembrie 2013 12:34:40
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.74 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;

int n;
ifstream in("cmap.in");

struct punct
{
    long long x;
    long long y;
}v[100010];

bool sortY(punct a,punct b)
{
    return (a.y < b.y);
}

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

double myDistance(punct a1, 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 firstCase(int left, int right)
{
    double d1,d2;
    d1 = 100000000000.0;

    for(int i = left; i < right ; i++ )
    {
        for(int j = i + 1 ; j<= right; j++)
        {
            d2 = myDistance(v[i], v[j]);
            if(d2 < d1)
            {
                d1 = d2;
            }
        }
    }
    sort(v+left, v + right + 1, sortY);
    return d1;
}

double secondCase(int left, int right, int middle, double distance)
{
    double d;
    int l = left;
    int r = middle+1;
    vector <punct> vec;

    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 - left < 7); i++)
    {
        for(int j = i+1; (j <= right) && (j-i < 7) ; j++)
        {
            d = myDistance(v[i],v[j]);
            if( d < distance)
            {
                distance = d;
            }
        }
    }

    return distance;
}

double devideAndConquer(int left, int right)
{
    double d;
    if(right - left <= 2)
    {
        d = firstCase(left, right);
        return d;
    }
    else
    {
        double s1,s2;
        int middle = left + (right - left) / 2;

        s1 = devideAndConquer(left, middle);
        s2 = devideAndConquer(middle + 1, right);
        if(s1>s2)
        {
            s1 = s2;
        }

        s2 = secondCase(left, right, middle, s1);
        if(s1>s2)
        {
            s1 = s2;
        }

        return s1;
    }
}

void read()
{
   in>>n;
   for(int i = 0 ; i<n; i++)
   {
       in>>v[i].x>>v[i].y;
   }
}

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