Cod sursa(job #2153868)

Utilizator andrew007Ciurianu Andrei andrew007 Data 6 martie 2018 15:42:39
Problema Cele mai apropiate puncte din plan Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 3.56 kb
#include <stdio.h>
#include <stdlib.h>

#define N 100005
#define ll long long
#define SWAP(tip, a, b) {tip t; \
                         t=a; a=b; b=t; }



typedef struct{
    int x;
    int y;
}PUNCT;

PUNCT arr[N],arr_second[N],aux1[N],aux2[N],aux3[N];
int n;


void merge_sort(PUNCT a[], int left, int right); ///dupa x
void merge(PUNCT a[], int left, int mid, int right);
void swap(PUNCT *x, PUNCT *y);
ll min(ll x, ll y);
ll dis(PUNCT x, PUNCT y);


ll calculate(int left, int right)
{
    if(left == right)
    {
        return pow(10,18);
    }
    if(right - left == 1)
    {
        if(arr_second[left].y > arr_second[right].y)
        {
            SWAP(PUNCT,arr_second[left],arr_second[right]);
        }
        return dis(arr[left],arr[right]);
    }
    int mid = (left + right) / 2;
    ll dis_minim = min(calculate(left, mid),calculate(mid + 1, right));

    int index = 0;
    int left_index = left;
    int right_index = mid + 1;

    while(left_index <= mid && right_index <= right)
    {
        if(arr_second[left_index].y < arr_second[right_index].y)
        {
            aux2[++index] = arr_second[left_index++];
        }
        else
        {
            aux2[++index] = arr_second[right_index++];
        }
    }
    while(left_index <= mid)
    {
        aux2[++index] = arr_second[left_index++];
    }
    while(right_index <= right)
    {
        aux2[++index] = arr_second[right_index++];
    }

    for(int i = left, j = 1; i <= right; i++){
        arr_second[i] = aux2[j++];
    }

    int t = 0;
    for(int i = left; i <= right; i++){
        if(fabs(1.0*arr_second[i].x - arr[mid].x) <= dis_minim){
            aux3[++t] = arr_second[i];
        }
    }

    for(int i = 1; i <= t; i++){
        for(int j = i + 1; j <= t && j < i + 8; ++j){
           dis_minim = min(1.0*dis_minim,1.0*dis(aux3[i],aux3[j]));
        }
    }
    return dis_minim;

}
int main(){
    FILE *f,*g;
    f = fopen("fisier.txt","r");
    g = fopen("cmap.out","w");

    fscanf(f,"%d",&n);
    for(int i = 1; i <= n; i++){
        fscanf(f,"%d%d",&arr[i].x, &arr[i].y);
    }

    mergeSort(arr, 1, n);

    for(int i = 1; i <= n; ++i){
        arr_second[i].x = arr[i].x;
        arr_second[i].y = arr[i].y;
    }

    ll answer = calculate(1, n);

    printf("%.8f\n",sqrt(answer));
    return 0;
}

void mergeSort(PUNCT a[], int left, int right)
{
   if (left < right)
   {
      int mid = left+(right-left)/2;
      mergeSort(a, left, mid);
      mergeSort(a, mid+1, right);
      merge(a, left, mid, right);
   }
}


void merge(PUNCT a[], int left, int mid, int right)
{
    int left_index = left;
    int right_index = mid + 1;
    int index = left;


    while(left_index <= mid && right_index <= right)
    {
        if(a[left_index].x <= a[right_index].x)
        {
            aux1[index++] = arr[left_index++];
        }
        else
        {
            aux1[index++] = arr[right_index++];
        }
    }

    if(left_index == mid + 1)
    {
        while(right_index <= right)
        {
            aux1[index++] = arr[right_index++];
        }
    }
    else
    {
        while(left_index <= mid)
        {
            aux1[index++] = arr[left_index++];
        }
    }

    for(int i = left; i <= right; i++)
    {
        arr[i] = aux1[i];
    }
}

ll min(ll x, ll y){
    if(x < y)
        return x;
    return y;
}
ll dis(PUNCT x, PUNCT y){
    return 1.0*(1.0*x.x - y.x) * (1.0*x.x - y.x) + 1.0*(1.0*x.y - y.y) * 1.0*(1.0*x.y - y.y);
}