////////////////////////////////////////////////////////////////////////////////

// Author: Julie Petrusa (991339)                                             //

// Due date: March 26, 2002                                                   //

// Description: The Closest-Pair Problem                                      //

// Given a set of points, this program determines the two points that are     //

// closest to each other in terms of distance. If there are more than one     //

// pair of points with the closest distance, all such pairs are identified.   //

// So the input is a set of n points and the output is the closest pair(s) of //

// points identified by their coordinates, along with the distance between    //

// them. Given the coordinates of two points P1(x1,y1,z1) and P2(x2,y2,z2),   //

// the distance between the points is given by |P1P2| = sqrt(pow(x2-x1)+      //

// pow(y2-y1)+pow(z2-z1)). A brute-force closest pair algorithm simply looks  //

// at all the (n 2) = 1/2n(n-1) point pairs and picks the ones with the       //

// smallest distance. This algorithm works for both 2-D and 3-D cases. The    //

// time complexity of this algorithm is O(n2).                                //

// Known bugs: none                                                           //

////////////////////////////////////////////////////////////////////////////////



#include <iostream.h>      // for console I/O

#include <fstream.h>       // for file I/O

#include <math.h>          // for sqrt

#include <stdlib.h>        // for system("PAUSE")



/******************************************************************************/

/******************************************************************************/



class Point

   {

   //---------------------------------------------------------------------------

   // fields

         private: double X;        // X-coordinate

                  double Y;        // Y-coordinate

                  double Z;        // Z-coordinate

   //---------------------------------------------------------------------------

   // constructors

         public: Point() : X(0), Y(0), Z(0)               // no arguments

            {

            }

         Point(int x, int y, int z) : X(x), Y(y), Z(z)    // three arguments

            {

            }

   //---------------------------------------------------------------------------

   // function getDistance

   // -returns the distance between two points using the distance formula

         double getDistance(Point p2)

            {

            return sqrt(pow(X - p2.X, 2) + pow(Y - p2.Y, 2) + pow(Z - p2.Z, 2));

            }

   //---------------------------------------------------------------------------

   // function lessThan

   // -compares two points

   // -returns true if the first point is lower than the second, false otherwise

         bool lessThan(Point p2)

            {

            if (X < p2.X)

               return true;

            else if (X == p2.X && Y < p2.Y)

               return true;

            else if (X == p2.X && Y == p2.Y && Z < p2.Z)

               return true;

            else

               return false;

            }

   //---------------------------------------------------------------------------

   // declarations

         friend istream& operator >> (istream& s, Point& p);  // overload >>

         friend ostream& operator << (ostream& s, Point& p);  // overload <<

   //---------------------------------------------------------------------------

   };

   //---------------------------------------------------------------------------

   // function overload >> operator

   // -gets Point from file with overloaded >> operator

   // -a point is expressed as a sequence of three numbers

   //  (x-coordinate, y-coordinate, z-coordinate) surrounded with parentheses

         istream&  operator >> (istream& s, Point& p)

            {

            char dummy;             // for "(" - ")" - ","

            s >> dummy >> p.X >> dummy >> p.Y >> dummy >> p.Z >> dummy;

            return s;

            }

   //---------------------------------------------------------------------------

   // function overload << operator

   // -sends Point to screen with overloaded << operator

   // -a point is expressed as a sequence of three numbers

   //  (x-coordinate, y-coordinate, z-coordinate) surrounded with parentheses

         ostream& operator << (ostream& s, Point& p)

            {

            s << "(" << p.X << "," << p.Y << "," << p.Z << ")";

            return s;

            }

   //---------------------------------------------------------------------------



/******************************************************************************/

/******************************************************************************/



int main()

   {

   cout << "\nAuthor: Julie Petrusa (991339).";             // display banner

   cout << "\nDue date: March 26, 2002.";

   cout << "\nDescription: The Closest-Pair Problem.";

   bool value = true;                         // initialize for do-while loop

   do

      {

      cout << "\n\nChoose one of the following options:";  // display options

      cout << "\n   1 --> Run the program";

      cout << "\n   2 --> Exit the program";

      cout << "\nAnswer: ";

      int answer;

      cin >> answer;

      if (answer == 1)                           // user wants to run program

         {

         cout << "\nPlease enter a file name: ";

         ifstream infile;

         char in[100];

         cin >> in;                       // get input file name from console

         infile.open(in);                 // open input file

         Point point;                     // create point

         const int MAX = 1200;            // maximum size of array

         Point points[MAX];               // create array of points

         int nPoints = 0;                 // initialize counter for points

         while (infile)                   // while file is valid

            {

            infile >> point;              // read points from file

            if (infile.eof())             // if end of file, stop

               {

               infile.close();

               break;

               }

            points[nPoints++] = point;    // store points in an array

            }

         double closest = points[0].getDistance(points[1]);  // used to compare

         double temp;

         for (int i=0; i<nPoints; i++)                       // iterate thru set

            for (int j=i+1; j<nPoints; j++)

               {

               temp = points[i].getDistance(points[j]);      // get distances

               if (temp < closest)

                  closest = temp;                            // store closest

               }

         cout << "\nThere are " << nPoints << " points in the set.";

         cout << "\nThe closest pairs are:\n";

         for (int i=0; i<nPoints; i++)

            for (int j=i+1; j<nPoints; j++)              // iterate thru set

               {

               temp = points[i].getDistance(points[j]);  // display closest pts

               if (temp == closest)                      // with distance

                  {

                  if (points[i].lessThan(points[j]))

                     cout <<"\n"<< points[i] <<" "<< points[j] <<" "<< closest;

                  else

                     cout <<"\n"<< points[j] <<" "<< points[i] <<" "<< closest;

                  }   

               }                                       // prints lower pt first

         }

      else                       // user wants to quit

         value = false;          // to end do-while

      } while (value == true);

   cout << "\n";

   system("pause");  // to view console

   return 0;         // end main

   }                 // end ClosestPairProblem