Cod sursa(job #2275169)

Utilizator vnedelcuVictor Andrei Nedelcu vnedelcu Data 2 noiembrie 2018 21:22:48
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.1 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>

const int dmax = 100000;
unsigned const int INF = (1ULL << 32) - 1;

struct point
{
    long long x,y;
};

point pointsX[dmax];
point pointsY[dmax];
point pointsL[dmax];

bool cmpX(point a, point b)
{
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

bool cmpY(point a, point b)
{
    if (a.y == b.y)
        return a.x < b.x;
    return a.y < b.y;
}

double distance(point a, point b)
{
    return sqrt((b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y));
}

double min_dist(int first, int last, int n)
{
    double best_distance = INF;
    double dist;
    int point_nr, mid, i, j;

    ///cazuri oprire
    point_nr = last - first + 1;
    if (point_nr == 1)
        return best_distance;
    if (point_nr == 2)
        return distance(pointsY[first],pointsY[last]);
    
    ///divide
    mid = first + (last - first)/2;
    best_distance = std::min(min_dist(first,mid,n), min_dist(mid+1,last,n));
    
    ///combina
    int u_bound = pointsY[mid].y + (int)best_distance;
    int l_bound = pointsY[mid].y - (int)best_distance;
    int Lsize = 0;
    for (i = 0; i < n; i++)
        if (l_bound <= pointsX[i].y && pointsX[i].y <= u_bound)
            pointsL[Lsize++] = pointsX[i];
    for (i = 0; i < Lsize - 1; i++)
    {
        j = i + 1;
        int count = 1;
        while (j < Lsize && count < 8)
        {
            dist = distance(pointsL[i],pointsL[j]);
            if (dist < best_distance)
                best_distance = dist;
            count++;
            j++;
        }
    }
    
    return best_distance;
}

int main()
{
    FILE *f;
    int i,n;

    f=fopen("cmap.in","r");
    fscanf(f,"%d",&n);
    for (i=0; i<n; i++)
    {
        fscanf(f,"%lld%lld",&pointsX[i].x,&pointsX[i].y);
        pointsY[i]=pointsX[i];
    }
    fclose(f);

    std::sort(pointsX,pointsX+n,cmpX);
    std::sort(pointsY,pointsY+n,cmpY);

    double ans = min_dist(0,n - 1,n);
    f=fopen("cmap.out","w");
    fprintf(f,"%f",ans);
    fclose(f);

    return 0;
}