#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define EXIT_SUCCESS     0
#define EXIT_COMMANDLINE 1
#define EXIT_FILEACCESS  2
#define EXIT_INPUTFORMAT 3
#define EXIT_MEMORY      4

#define LUNGHEZZA 256
#define INFINITE 1e10;

enum _boolean {FALSE = 0, TRUE = 1};
typedef enum _boolean boolean;


typedef struct _point point;
typedef point* PointVector;

struct _point
{
  int id;
  int x, y;
};


void ReadCommandLine (int argc, char *argv[], char *InputFile);

void LoadData (char *InputFile, int *pNumPoints, PointVector *pPoint);

double Distanza (point P1, point P2);

void SortPointsByX (int s, int d, PointVector Aux, PointVector Point);

void FindClosestPair (int s, int d, PointVector Aux, PointVector Point, point *P1Min, point *P2Min, double *pDist);


int main (int argc, char *argv[])
{
  char InputFile[LUNGHEZZA];
  int NumPoints;
  PointVector Point, Aux;
  point P1, P2;
  double Dist;


  // 1) Interpretazione della linea di comando
  ReadCommandLine(argc,argv,InputFile);

  // 2) Caricamento dei dati
  LoadData(InputFile,&NumPoints,&Point);

  // 3) Allocazione delle strutture dati ausiliarie
  Aux = (PointVector) calloc(NumPoints+1,sizeof(point));
  if (Aux == NULL)
  {
    printf("Not enough memory to allocate the axuiliary vector of points!\n");
    exit(EXIT_MEMORY);
  }

  // 4) Elaborazione
  SortPointsByX(1,NumPoints,Aux,Point);
  FindClosestPair(1,NumPoints,Aux,Point,&P1,&P2,&Dist);

  // 5) Deallocazione delle strutture dati ausiliarie
  free(Aux);

  // 6) Stampa della soluzione
  printf("Le colonie %d e %d restano separate al massimo %d giorni dopo l'impianto\n",
         P1.id,P2.id,(int)(Dist/2.0));

  // 7) Deallocazione delle strutture dati principali
  free(Point);

  return EXIT_SUCCESS;
}


void ReadCommandLine (int argc, char *argv[], char *InputFile)
{
  if (argc != 2)
  {
    printf("The command line has a wrong format!\n");
    printf("%s [InputFile]\n",argv[0],InputFile);
    exit(EXIT_COMMANDLINE);
}

  strcpy(InputFile,argv[1]);
}


void LoadData (char *InputFile, int *pNumPoints, PointVector *pPoint)
{
  FILE *fInputFile;
  int p;

  fInputFile = fopen(InputFile,"r");
  if (fInputFile == NULL)
  {
    printf("File %s could not be opened!\n",InputFile);
    exit(EXIT_FILEACCESS);
  }

  if (fscanf(fInputFile,"%d",pNumPoints) != 1)
  {
    printf("The number of points could not be found in file %s!\n",InputFile);
    exit(EXIT_INPUTFORMAT);
  }

  *pPoint = (PointVector) calloc(*pNumPoints+1,sizeof(point));
  if (*pPoint == NULL)
  {
    printf("Not enough memory to allocate the vector of points!\n");
    exit(EXIT_MEMORY);
  }

  for (p = 1; p <= *pNumPoints; p++)
  {
    if (fscanf(fInputFile,"%d %d",&(*pPoint)[p].x,&(*pPoint)[p].y) != 2)
    {
      printf("The coordinates of point %d could not be found in file %s!\n",p,InputFile);
      exit(EXIT_INPUTFORMAT);
    }
    (*pPoint)[p].id = p;
  }

  fclose(fInputFile);
}


double Distanza (point P1, point P2)
{
  return sqrt( (P1.x-P2.x)*(P1.x-P2.x) + (P1.y-P2.y)*(P1.y-P2.y) );
}


void MergePointsByX (int s, int m, int d, PointVector Aux, PointVector Point)
{
  int p, p1, p2;

  p1 = s;
  p2 = m+1;
  for (p = s; p <= d; p++)
    if (p1 > m)
      Aux[p] = Point[p2++];
    else if (p2 > d)
      Aux[p] = Point[p1++];
    else if (Point[p1].x <= Point[p2].x)
      Aux[p] = Point[p1++];
    else
      Aux[p] = Point[p2++];

  for (p = s; p <= d ; p++)
    Point[p] = Aux[p];
}


void SortPointsByX (int s, int d, PointVector Aux, PointVector Point)
{
  int m;

  if (s >= d)
    return;
  else
  {
    m = (s+d)/2;
    SortPointsByX(s,m,Aux,Point);
    SortPointsByX(m+1,d,Aux,Point);
    MergePointsByX(s,m,d,Aux,Point);
  }
}


void MergePointsByY (int s, int m, int d, PointVector Aux, PointVector Point)
{
  int p, p1, p2;

  p1 = s;
  p2 = m+1;
  for (p = s; p <= d; p++)
    if (p2 > d)
      Aux[p] = Point[p1++];
    else if (p1 > m)
      Aux[p] = Point[p2++];
    else if (Point[p1].y <= Point[p2].y)
      Aux[p] = Point[p1++];
    else
      Aux[p] = Point[p2++];

  for (p = s; p <= d ; p++)
    Point[p] = Aux[p];
}

void FindClosestPair (int s, int d, PointVector Aux, PointVector Point, point *P1Min, point *P2Min, double *pDist)
{
  int p, m, pp;
  int x;
  point P1Min1, P2Min1, P1Min2, P2Min2;
  double DistMin1, DistMin2, delta;
  point Temp;
  int s2, d2;

  if (d-s < 1)
  {
    P1Min->id = P1Min->x = P1Min->y = 0;
    P2Min->id = P2Min->x = P2Min->y = 0;
    *pDist = INFINITE;
  }
  else if (d-s == 1)
  {
    *pDist = Distanza(Point[s],Point[d]);
    *P1Min = Point[s];
    *P2Min = Point[d];
    // Ordina i due punti per y crescente
    if (Point[s].y > Point[d].y)
    {
      Temp = Point[s];
      Point[s] = Point[d];
      Point[d] = Temp;
    }
  }
  else
  {
    // Divide: determina i due sottovettori e la coordinata che divide in due il piano
    m = (s+d)/2;
    x = Point[m].x;

    // Impera: risolve i sottoproblemi, ottenendo per ognuno i due punti piu' vicini e la loro distanza
    FindClosestPair(s,m,Aux,Point,&P1Min1,&P2Min1,&DistMin1);
    FindClosestPair(m+1,d,Aux,Point,&P1Min2,&P2Min2,&DistMin2);

    // Combina: 1) trova la coppia di punti piu' vicini da un lato del taglio
    *P1Min = P1Min1;
    *P2Min = P2Min1;
    *pDist = DistMin1;
    if (DistMin2 < *pDist)
    {
      *P1Min = P1Min2;
      *P2Min = P2Min2;
      *pDist = DistMin2;
    }
    delta = *pDist;

    // Combina: 2) Filtra via i punti lontani dalla mezzeria (l'ascissa differisce da x piu' di delta)
    // Nota: i punti sono stati riordinati per y crescenti, per cui non sono piu' adiacenti a m.
    s2 = m;
    for (p = m-1; p >= s; p--)
      if (x - Point[p].x < delta)
      {
		s2--;
		Temp = Point[s2];
		Point[s2] = Point[p];
		Point[p] = Temp;
	  }

    d2 = m;
    for (p = m+1; p <= d; p++);
      if (Point[p].x - x < delta)
      {
		d2++;
		Temp = Point[d2];
		Point[d2] = Point[p];
		Point[p] = Temp;
	  }

    // Combina: 3) fonde le due sottoliste di sinistra e destra in una lista sola ordinata per y crescenti
    MergePointsByY(s2,m,d2,Aux,Point);

    // Combina: 4) per trovare la coppia di punti piu' vicini a cavallo del taglio
    // valuta la distanza di ciascuno dai 5 punti piu' vicini nella sequenza ordinata;
    // per simmetria, la valuta solo rispetto ai 3 punti successivi
    for (p = s2; p <= d2; p++)
    {
      if ( (p+1 <= d2) && (Distanza(Aux[p],Aux[p+1]) < *pDist) )
      {
        *pDist = Distanza(Aux[p],Aux[p+1]);
        *P1Min = Aux[p];
        *P2Min = Aux[p+1];
      }
      if ( (p+2 <= d2) && (Distanza(Aux[p],Aux[p+2]) < *pDist) )
      {
        *pDist = Distanza(Aux[p],Aux[p+2]);
        *P1Min = Aux[p];
        *P2Min = Aux[p+2];
      }
      if ( (p+3 <= d2) && (Distanza(Aux[p],Aux[p+3]) < *pDist) )
      {
        *pDist = Distanza(Aux[p],Aux[p+3]);
        *P1Min = Aux[p];
        *P2Min = Aux[p+3];
      }
    }
  }
}