Let x, y, and z denote the three coordinate axes in the three dimensional space R3 . A point p ∈ R3 is specified by its coordinates along the three axes: p = (x(p), y(p), z(p)). For p, q ∈ R3 , we say

void setMaximal(); // Sets maximal to true: The point is maximal double getX() const; double getY() const; bool getMaximal() const; bool operator<(const Point& p) const; // Returns (*this < p) friend istream& operator>>(istream& ISObj, Point& p); // Inputs a single point: Its x, y and z coords friend ostream& operator<<(ostream& OSObj, const Point& p); // Outputs a single point: Its x, y and z coords private:

double x = 0, y = 0, z = 0; // Coords of the point bool maximal = false; // Whether the point is maximal }; typedef map mapdd; void inputPoints(ifstream& infile, Point* points, int* numPoints); void findMaximal(Point* points, int numPoints, int* maxNum); void printMaximal(ofstream& outfile, Point* points, int numPoints, int maxNum); int main(int argc, char *argv[]) { if (argc != 3) { // Error check } ifstream infile(argv[1]); ofstream outfile(argv[2]); for (int i=1; i<=10; i++) // Iterate on 10 sets of points { int numPoints = 0; // Number of points in the i-th set Point points[1000]; // points[0..(numPoints-1)] inputPoints( ); // Reads the i-th input set sort( ); // Sorts points[0..(numPoints-1)] int maxNum = 0; // Number of maximal points in the i-th set findMaximal( ); // Finds the maximal points outfile << "Output for " << i << "-th Set of Points\n"; printMaximal( ); } files close(); } void inputPoints( ) // Inputs all the points into points[] { ....

infile >> points[i]; } void printMaximal(ofstream& outfile, Point* points, int numPoints, int maxNum) // Outputs the maximal elements in points[] { outfile << "Input Size = " << numPoints << endl; outfile << "MaxNum = " << maxNum << endl << endl; outfile << "Maxima(S) (x, y, z)\n"; for (int i=0; i < numPoints; ++i) if (points[i].getMaximal()) outfile << i << " " << points[i] << endl; outfile << "\n--------------------------------------------\n\n"; } void findMaximal(Point* points, int numPoints, int* maxNum) // Finds the maximal elements in points[0..(numPoints-1)] { mapdd bst; // Keeps the 2-d maxima (in the (x,y)-plane) // of the points seen so far.

// Keeps (key=y_coord, value=x_coord) pairs.

bst[1.0] = 0.0; // Inserts (key 1.0, value 0.0) into bst *maxNum = 0; double xcoord, ycoord; for (int i = numPoints-1; i >= 0; i--) { xcoord = points[i].getX(); ycoord = points[i].getY(); mapdd::iterator successor = bst.???

.

.

.

} }