Cod sursa(job #3369531)

Utilizator DragosVNVisanescu Dragos Nicholas DragosVN Data 21 octombrie 2026 00:18:41
Problema Cele mai apropiate puncte din plan Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 5.95 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int n;
const long long INF = 1e18;

struct point{
long long x,y;
}v[100005],aux[100005],ind[100005];

/*
 idea:

 1. sort points by x
 2. start splitting in divide and conquer fashion
 3. when you get to 2 or 3 points just manually compute min distance between all pairs
 4. !! recursing up: !!

    suppose on the left side we have the set of points Pl and on the right Pr
    all we know is min distance between any pair of 2 points on the left and separately on the right

    recall our target is min distance between any 2 points of the whole set

    so we can literally verify if the total minimum improves by left_min or right_min

    now, do we really need to check all the possible pair of points from the left and right ?

    answer is a happy no

    we only need to check the pairs of points that might have the chance to result in a smaller distance

    than our current d_min

    question is what points are those?

    suppose P1(x1,y1) belongs to left half and P2(x2,y2) belongs to right half

    recall distance formula d = sqrt ( ( x1 - x2 ) ^ 2 + ( y1 - y2 ) ^ 2 )

    if abs(x1 - x2) >= d_min this will already result in a final distance d >= d_min

    same happends if abs(y1 - y2) >= d_min

    so we literally must only check the pair of points that satisfy simultaneously:

    | x2 - x1 | < d_min
    | y2 - y1 | < d_min


    now if we get the dividing mid line between the 2 zones ( given by mean of x values of
    the rightmost point in the left and leftmost point on the right )

    we can also automatically tell that we only consider the points on the left that satisfy:

    mid - d_min <= x1 <= mid

    and on the right that satisfy: mid <= x2 <= mid + d_min

    because otherwise they would directly have a greater distance than d_min no matter what the

    other point in the pair is.

    now for any 2 points on the same side we know that the min distance between any 2 is

    at most d_min ( both on the left and on the right ) !!!

    thus in a square of d_min x d_min there can be exactly 4 points ( all in the corners ) for this to be preserved

    lets take all the points that satisfy the x condition ( both on the left and the right ) call this set P

    now sort P by y

    so any 2 consecutive points in this P set either are on the same side and their distance is >= d_min

    or one is on the left and one is on the right, case in which the distance could be smaller

    interesting part is this: say we are now on a point Pl(xl,yl)

    all points on the left must be positioned above yl + d_min clearly

    but the same thing happends on the right, consider a point on the right Pr(xr,yr)

    If it indeed is at a smaller distance than d_min to P1, it also imposes the same distance upwards to the next

    point of yr + d_min.

    Worst case of this is when all points are situated right in the rectangle corners with one corner in P1 or P2

    now the distance between all these points is d_min and they are 8 ( 4 on the left, 4 on the right and 2 are

    identical right on the dividing line )

    nice


*/

long long calc_dist2(struct point p1, struct point p2)
{
    return (p1.x-p2.x) * (p1.x-p2.x)  + (p1.y-p2.y) * (p1.y-p2.y);
}

int cmp_x(const void *a, const void *b)
{
    const struct point *p = a, *q = b;
    return (p->x > q->x) - (p->x < q->x);
}

void swap(int l,int r)
{
    v[l].y ^= v[r].y;
    v[r].y ^= v[l].y;
    v[l].y ^= v[r].y;

    v[l].x ^= v[r].x;
    v[r].x ^= v[l].x;
    v[l].x ^= v[r].x;
}
long long min2(long long a,long long b)
{
    if(a>b)
        return b;

    return a;
}
void merge_sides(int l1, int r1,int l2, int r2)
{

    int i = l1, j = l2, k = 0;

    while(i <= r1 && j <= r2)
    {
        if(v[i].y < v[j].y)
        {
            aux[++k] = v[i];
            i++;
        }
        else if(v[i].y > v[j].y)
        {
            aux[++k] = v[j];
            j++;
        }
        else
        {
            aux[++k] = v[i];
            i++;
            aux[++k] = v[j];
            j++;
        }
    }

    while(i <= r1)
    {
        aux[++k] = v[i];
        i++;
    }
    while(j <= r2)
    {
        aux[++k] = v[j];
        j++;
    }

    for(int i=1,j=l1;i<=k;i++,j++)
    v[j] = aux[i];

}

long long solve(int l, int r)
{
    if(l >= r)
        return INF;

    if(r-l+1 == 2)
    {
        if(v[l].y > v[r].y)
        swap(l,r);

        return calc_dist2(v[l],v[r]);
    }

    if(r-l+1 == 3)
    {
        if(v[l].y > v[r].y)
            swap(l, r);

        if(v[l].y > v[l+1].y)
            swap(l, l+1);

        if(v[l+1].y > v[r].y)
            swap(l+1, r);

        long long d1 = calc_dist2(v[l], v[l+1]);
        long long d2 = calc_dist2(v[l+1], v[r]);
        long long d3 = calc_dist2(v[l], v[r]);

        return min2(min2(d1,d2),d3);
    }

    int mid = (l+r)/2;
    long long midx = (v[mid].x + v[mid+1].x) / 2;

    long long min_left = solve(l, mid);
    long long min_right = solve(mid+1, r);
    long long d_min = min2(min_left, min_right);

    merge_sides(l,mid,mid+1,r);

    int k = 0;

    for(int i=l;i<r;i++)
        if( ( midx <= v[i].x && v[i].x - midx <= d_min) || (midx >= v[i].x && midx - v[i].x <= d_min))
            ind[++k] = v[i];    // only points closer than d_min to the dividing line

    for(int i=1;i<=k;i++)
        for(int j=1;j<8 && i+j <=k;j++)
            d_min = min2(d_min,calc_dist2(ind[i],ind[i+j]));

    return d_min;
}

int main()
{

    FILE *fin = fopen("cmap.in","r");
    FILE *fout = fopen("cmap.out", "w");

    fscanf(fin, "%d", &n);

    for(int i=1;i<=n;i++)
    {
        fscanf(fin, "%lld", &v[i].x);
        fscanf(fin, "%lld", &v[i].y);
    }


    qsort(v+1, n, sizeof(struct point), cmp_x);

    fprintf(fout, "%.6f", sqrt( solve(1,n) ) );


    fclose(fin);

    return 0;
}