// --- Inicio del programa -----------------------------------------------------

#include<iostream>
#include<fstream>
#include<cmath>
#include<iomanip>

using namespace std;

void leer_datos(double coordenadas[100][2], int &n_ciudades);
double coordenada_y_de_la_ciudad_mas_al_norte(double coordenadas[100][2], int n_ciudades);
double distancia_de_ciudades_mas_lejanas(double coordenadas[100][2], int n_ciudades);
void calcular_el_centro_de_la_ciudad(double coordenadas[100][2], int n_ciudades, double &x_centro, double &y_centro);
void buscar_ciudades_perifericas(double coordenadas[100][2], int n_ciudades, double x_centro, double y_centro, double ciudades_perifericas[2][2]);
void guardar_resultados(double ciudades_perifericas[2][2]);


int main() // Este main no debe ser modificado
{
  double coordenadas[100][2], ciudades_perifericas[2][2], distancia, coordenada_y;
  double x_centro, y_centro;
  int    n_ciudades;

  leer_datos(coordenadas, n_ciudades);

  coordenada_y = coordenada_y_de_la_ciudad_mas_al_norte(coordenadas, n_ciudades);

  distancia = distancia_de_ciudades_mas_lejanas(coordenadas, n_ciudades);

  cout << "\n\n";
  cout << "La coordenada Y de la ciudad mas al norte es: " << coordenada_y;
  cout << "\n";
  cout << "Las ciudades mas lejanas se encuentran a una distancia de: " << distancia;
  cout << "\n\n";

  calcular_el_centro_de_la_ciudad(coordenadas, n_ciudades, x_centro, y_centro);

  cout << "El centro de la ciudad es: " << x_centro << "   " << y_centro << "\n\n";

  buscar_ciudades_perifericas(coordenadas, n_ciudades, x_centro, y_centro, ciudades_perifericas);

  guardar_resultados(ciudades_perifericas);

  return 0;
}

void leer_datos(double coordenadas[100][2], int &n_ciudades)
{
  ifstream arch;
  arch.open("ciudades.txt");

  if(!arch.good())
    {
      cout << "\n Error al intentar abrir el archivo \n";
      exit(0);
    }

  arch >> n_ciudades;
  for(int k=0; k<n_ciudades; k++)
    for(int n=0; n<2; n++)
      arch >> coordenadas[k][n];

  arch.close();
}

double coordenada_y_de_la_ciudad_mas_al_norte(double coordenadas[100][2], int n_ciudades)
{
  double y;
  for(int k=0; k<n_ciudades; k++)
    if( (k==0) || (coordenadas[k][1]>y) )
      y = coordenadas[k][1];

  return y;
}

double distancia_de_ciudades_mas_lejanas(double coordenadas[100][2], int n_ciudades)
{
  double max_dist = 0;
  for(int k=0; k<n_ciudades; k++)
    for(int n=k+1; n<n_ciudades; n++)
      {
        double dx   = coordenadas[k][0]-coordenadas[n][0];
        double dy   = coordenadas[k][1]-coordenadas[n][1];
        double dist = sqrt(dx*dx + dy*dy);
        if( max_dist < dist )
          max_dist = dist;
      }

  return max_dist;
}

void calcular_el_centro_de_la_ciudad(double coordenadas[100][2], int n_ciudades, double &x_centro, double &y_centro)
{
  x_centro = 0;
  y_centro = 0;
  for(int k=0; k<n_ciudades; k++)
    {
      x_centro += coordenadas[k][0];
      y_centro += coordenadas[k][1];
    }
  x_centro = x_centro/n_ciudades;
  y_centro = y_centro/n_ciudades;
}

void buscar_ciudades_perifericas(double coordenadas[100][2], int n_ciudades, double x_centro, double y_centro, double ciudades_perifericas[2][2])
{
  // Hace una copia de las ciudades desplazadas al centro y luego las ordena parcialmente según la distancia al centro
  double nc[100][2]; 

  for(int k=0; k<n_ciudades; k++)
    {
      nc[k][0] = coordenadas[k][0]-x_centro;
      nc[k][1] = coordenadas[k][1]-y_centro;
    }

  // Algoritmo de ordenación: solo dos pasadas (no es necesario el algoritmo completo)
  for(int n=0; n<2; n++)
    for(int k=n_ciudades-1; k>0; k--)
      {
        double dist1 = sqrt(nc[k-1][0]*nc[k-1][0] + nc[k-1][1]*nc[k-1][1]);
        double dist2 = sqrt(nc[k  ][0]*nc[k  ][0] + nc[k  ][1]*nc[k  ][1]);
        if(dist2 > dist1)
          {
            double x   = nc[k][0];
            double y   = nc[k][1];
            nc[k][0]   = nc[k-1][0];
            nc[k][1]   = nc[k-1][1];
            nc[k-1][0] = x;
            nc[k-1][1] = y;
          }
      }

  ciudades_perifericas[0][0] = nc[0][0]+x_centro;
  ciudades_perifericas[0][1] = nc[0][1]+y_centro;
  ciudades_perifericas[1][0] = nc[1][0]+x_centro;
  ciudades_perifericas[1][1] = nc[1][1]+y_centro;
}

void guardar_resultados(double ciudades_perifericas[2][2])
{
  ofstream arch;
  arch.open("ciudades_perifericas.txt");

  arch << "Ciudad 1:  X = " << fixed << setprecision(1) << ciudades_perifericas[0][0] << "\t  Y = "  << fixed << setprecision(1) << ciudades_perifericas[0][1];
  arch << "\n";
  arch << "Ciudad 2:  X = " << fixed << setprecision(1) << ciudades_perifericas[1][0] << "\t  Y = "  << fixed << setprecision(1) << ciudades_perifericas[1][1];
  arch << "\n";

  arch.close();
}

// --- Fin del programa --------------------------------------------------------