/****************************************************************************/
/*                               LIBRERIE                                   */
/****************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/****************************************************************************/
/*                                 MACRO                                    */
/****************************************************************************/
#define SWAP(a,b) {void *tmp; tmp = *a; *a = *b; *b = tmp;}
#define COMPARE(a,b) ( (*(int *)a > *(int *)b) )

/****************************************************************************/
/*                        FORWARD DECLARATIONS                              */
/****************************************************************************/
int partition(void **S,int l,int r);
void quicksort(void **v,int l,int r);
void find_ij(int punto, int *X, int *Y, int **X_ORD, int **Y_ORD, int base, int altezza);

/****************************************************************************/
/*                                 MAIN                                     */
/****************************************************************************/
int main(){
    int i,              /* indice di scorrimento                            */
        n,              /* numero di punti                                  */
        *X,             /* puntatore alle coordinate X                      */
        *Y,             /* puntatore alle coordinate Y                      */
        **X_ORD,        /* puntatore al vettore X per ordinarlo             */
        **Y_ORD,        /* puntatore al vettore Y per ordinarlo             */
        base,           /* base delle celle                                 */
        altezza,        /* altezza delle celle                              */
        n_row,n_col,    /* numero righe/colonne                             */
    FILE *f;
       
    /* === LETTURA FILE =================================================== */
    f = fopen("punti.txt","rt");

    fscanf(f,"%d",&n);
   
    X = (int *) malloc (n*sizeof(int));
    X_ORD = (int **) malloc (n*sizeof(int *));

    Y = (int *) malloc (n*sizeof(int));
    Y_ORD = (int **) malloc (n*sizeof(int *));

    for(i=0;i<n;i++){
        fscanf(f,"%d %d",&X[i],&Y[i]); /* ascissa, ordinata */
        X_ORD[i] = &X[i];
        Y_ORD[i] = &Y[i];
    }
    fclose(f);
    /* ============================================== FINE LETTURA FILE === */

    for (i=0;i<n;i++)
        printf("pt %d: (%2d,%2d)\n",i,X[i],Y[i]);

    /* ordiniamo le i vettori per poterne utilizzare minimi e massimi */
    quicksort(X_ORD,0,n-1);
    quicksort(Y_ORD,0,n-1);

    printf("xmin = %d, xmax = %d\n",*X_ORD[0],*X_ORD[n-1]);
    printf("ymin = %d, ymax = %d\n",*Y_ORD[0],*Y_ORD[n-1]);
   
    /* otteniamo base/altezza delle celle */
    for(i=1;((base    = (*X_ORD[i] - *X_ORD[0])) == 0); i++);
    for(i=1;((altezza = (*Y_ORD[i] - *Y_ORD[0])) == 0); i++);
    printf("base = %d, altezza = %d\n",base,altezza);

    /* calcoliamo numero di righe e di colonne */
    n_row = ((*Y_ORD[n-1] - *Y_ORD[0])%altezza)?((*Y_ORD[n-1] - *Y_ORD[0])/altezza)+1:((*Y_ORD[n-1] - *Y_ORD[0])/altezza+2);
    n_col = ((*X_ORD[n-1] - *X_ORD[0])%base   )?((*X_ORD[n-1] - *X_ORD[0])/base   )+1:((*X_ORD[n-1] - *X_ORD[0])/base   +2);
   
    printf("n_row = %d, n_col = %d\n",n_row,n_col);

    /* applichiamo la funzione FIND(i,j) per ottenere le celle delle matrici contenenti i punti */
    for(i=0;i<n;i++)
        find_ij(i,X,Y,X_ORD,Y_ORD,base,altezza);

    return 0;
}

/****************************************************************************/
/*                                QUICKSORT                                 */
/****************************************************************************/
int partition(void **S,int l,int r)
{
    int i,j;
    i = l - 1;
    j = r + 1;
    for(;;){
        while( COMPARE(S[r],S[++i]) );
        while( COMPARE(S[--j],S[r]) )
            if(j==1) break;
        if(i>=j) break;
        SWAP(&S[i],&S[j]);
    }
    SWAP(&S[r],&S[i]);
    return i;
}

void quicksort(void **v,int l,int r){
    int i;
    if (r<=l) return;
    i = partition(v,l,r);
    quicksort(v,l,i-1);
    quicksort(v,i+1,r);
}

/****************************************************************************/
/*                               FIND(i,j)                                  */
/****************************************************************************/
void find_ij(int punto, int *X, int *Y, int **X_ORD, int **Y_ORD, int base, int altezza)
{
    int i,j;
    i = (X[punto]-(*X_ORD[0]))/base;
    j = (Y[punto]-(*Y_ORD[0]))/altezza;
    printf("%d = (%2d,%2d)->(%2d,%2d)\n",punto,X[punto],Y[punto],i,j);
}