#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 FindClosestPair (int s, int d, PointVector Point, point *P1Min, point *P2Min, double *pDist);


int main (int argc, char *argv[])
{
  char InputFile[LUNGHEZZA];
  int   NumPoints;
  PointVector Point;
  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

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

  // 5) Deallocazione delle strutture dati ausiliarie

  // 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 FindClosestPair (int s, int d, PointVector Point, point *P1Min, point *P2Min, double *pDist)
{
  int p;
  double dist;

  if (s >= d)
  {
    P1Min->id = P1Min->x = P1Min->y = 0;
    P2Min->id = P2Min->x = P2Min->y = 0;
    *pDist = INFINITE;
  }
  else if (d == s+1)
  {
    *P1Min = Point[1];
    *P2Min = Point[2];
    *pDist = Distanza(Point[1],Point[2]);
  }
  else
  {
    FindClosestPair(s,d-1,Point,P1Min,P2Min,pDist);
    for (p = s; p < d; p++)
    {
      dist = Distanza(Point[p],Point[d]);
      if (dist < *pDist)
      {
        *pDist = dist;
        *P1Min = Point[p];
        *P2Min = Point[d];
      }
    }
  }
}