Cod sursa(job #3369532)

Utilizator DerpimusRexPetcu Antonio DerpimusRex Data 21 octombrie 2026 00:33:21
Problema Cele mai apropiate puncte din plan Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.64 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>

typedef long long int ll;

struct pair{
    ll x;
    ll y;
};

ll dist(struct pair *a, struct pair *b){
    return (a->x - b->x)*(a->x - b->x) + (a->y - b->y) * (a->y - b->y);
}

bool cmp_less(struct pair *a, struct pair *b){
    if(a->x == b->x)return a->y < b->y; else return a->x < b->x;
}
void combine(struct pair *v, struct pair *aux, int begin, int mid, int end){
    //merges (interclasare) vectors [v+begin, v+mid] and [v+mid+1, v+end]
    int i = begin, j = mid+1, auxpos = begin;
    while(i<=mid && j<=end){
        if(cmp_less(v+i, v+j)){
            aux[auxpos++] = v[i];
            i++;
        } else {
            aux[auxpos++] = v[j];
            j++;
        }
    }
    while(i<=mid){
        aux[auxpos++] = v[i]; i++;
    }
    while(j<=end){
        aux[auxpos++] = v[j]; j++;
    }
    for(i = begin; i<=end; i++)v[i] = aux[i]; 
}
void sort(struct pair *v, struct pair *aux, int begin, int end){
    if(begin >= end) return;
    int mid = (begin+end)/2;
    sort(v, aux, begin, mid); sort(v, aux, mid+1, end);
    combine(v, aux, begin, mid, end);
}

void swap(struct pair *a, struct pair *b){
    a->x = a->x + b->x;
    b->x = a->x - b->x;
    a->x = a->x - b->x;

    a->y = a->y + b->y;
    b->y = a->y - b->y;
    a->y = a->y - b->y;
}

ll solve(struct pair *x, struct pair *y, struct pair *aux, int begin, int end){
    if(begin >= end) return 9*1e18;
    if(begin == end-1){
        if(!cmp_less(y+begin, y+end))swap(y+begin, y+end);
        return dist(x+begin, x+end);
    }
    
    int mid = (begin+end)/2;

    ll sd = solve(x, y, aux, begin, mid), rd = solve(x, y, aux, mid+1, end);
    ll mind = (sd<rd) ? sd : rd;
    int auxpos = 0;
    combine(y, aux, begin, mid, end);
    for(int i = begin; i<=end; i++){
        if(abs(y[i].y - x[mid].x)*(y[i].y - x[mid].x)<=mind)aux[auxpos++] = y[i];
    }
    for(int i = 0; i<auxpos; i++){
        for(int j = 1; j<=7 && i+j<auxpos; j++){
            ll newdist = dist(aux + i, aux + (i+j));
            mind = (newdist < mind) ? newdist:mind;
        }
    }
    return mind;
}

int main(){
    FILE* fin;
    fin = fopen("cmap.in", "r");
    int n;
    fscanf(fin, "%d", &n);
    struct pair x[n], y[n], aux[n];
    for(int i = 0; i<n; i++){
        ll a, b;
        fscanf(fin, "%lld" "%lld", &a, &b);
        x[i].x = a; x[i].y = b;
    }
    fclose(fin);
    sort(x, aux, 0, n-1);
    for(int i = 0; i<n; i++){
        y[i].x = x[i].y;
        y[i].y = x[i].x;
    }
    FILE* fout;
    fout = fopen("cmap.out", "w");
    fprintf(fout,"%.6lf", sqrt(solve(x, y, aux, 0, n-1)));
    fclose(fout);
    return 0;   
}