Monotone_Chain

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>

using namespace std;

struct Point
{
      int x,y;
      friend std::ostream &operator << (std::ostream &output,const Point &p);
      friend std::istream &operator >> (std::istream &input,Point &p);
};

bool operator == (Point a,Point b)
{
     return (a.x == b.x && a.y == b.y);
}

std::ostream &operator << (std::ostream &output,const Point &p)
{
        output<<"( "<<p.x<<" , "<<p.y<<" ) ";
        return output;
}



std::istream &operator >> (std::istream &input,Point &p)
{
        input>>p.x>>p.y;;
        return input;
}


template<class T>
class Link
{
      private:
              T data;
              Link<T> *next;
              Link<T> *previous;
      public:
             Link(T data);
             void displayLink();
             T getData();
             void setData(T data);
             Link<T> *getNext();
             void setNext(Link<T> *next);
             Link<T> *getPrevious();
             void setPrevious(Link<T> *previous);
             template<class U> friend std::ostream& operator<< (std::ostream& print, Link<U>& obj);

};

template<class T>
Link<T>::Link(T data)
{
     setData(data);
     setNext(NULL);
     setPrevious(NULL);

}

template<class T>
void Link<T>::displayLink()
{
     std::cout<<getData()<<" ";
}

template<class T>
T Link<T>::getData()
{
     return data;
}

template<class T>
void Link<T>::setData(T data)
{
     this->data = data;
}

template<class T>
Link<T> *Link<T>::getNext()
{
      return next;
}

template<class T>
void Link<T>::setNext(Link<T> *next)
{
      this->next = next;
}

template<class T>
Link<T> *Link<T>::getPrevious()
{
      return previous;
}

template<class T>
void Link<T>::setPrevious(Link<T> *previous)
{
      this->previous = previous;
}


template <class U>
std::ostream& operator<<(std::ostream& print, Link<U> & L)
{
        print << L.getData();
        return print;
}

template<class T>
class DoublyLinkedList
{
      private:
              Link<T> *first;
              Link<T> *last;
              void enqueue(Link<T> *x);
              Link<T> *dequeue();
      public:
             DoublyLinkedList();
             ~DoublyLinkedList();
             Link<T> *getFirst();
             void setFirst(Link<T> *first);
             Link<T> *getLast();
             void setLast(Link<T> *first);
             bool isEmpty();
             Link<T> *find(T key);
             void insertFirst(T dd);
             void insertLast(T dd);
             void deleteFirst();
             void deleteLast();
             bool insertAfter(T key,T dd);
             void deleteKey(T key);
             void displayForward();
             void displayBackward();
             void concat(DoublyLinkedList<T> &L);
             void quickSort(int (*Compare)(T,T));
};

template<class T>
DoublyLinkedList<T>::DoublyLinkedList()
{
    setFirst(NULL);
    setLast(NULL);
}

template<class T>
DoublyLinkedList<T>::~DoublyLinkedList()
{
    while(!isEmpty())
    {
        deleteFirst();
    }
}

template<class T>
Link<T> *DoublyLinkedList<T>::getFirst()
{
       return first;
}

template<class T>
void DoublyLinkedList<T>::setFirst(Link<T> *first)
{
     this->first = first;
}

template<class T>
Link<T> *DoublyLinkedList<T>::getLast()
{
       return last;
}

template<class T>
void DoublyLinkedList<T>::setLast(Link<T> *last)
{
     this->last = last;
}

template<class T>
bool DoublyLinkedList<T>::isEmpty()
{
     return getFirst()==NULL;
}

template<class T>
 Link<T> *DoublyLinkedList<T>::find(T key)
 {
         Link<T> *current = getFirst();
         while(current != NULL && !(current->getData == key))
               current = current->getNext();
         return current;
 }

 template<class T>
 void DoublyLinkedList<T>::insertFirst(T dd)
 {
      Link<T> *newLink = new Link<T>(dd);
      if(isEmpty())
           setLast(newLink);
      else
          getFirst()->setPrevious(newLink);
      newLink->setNext(getFirst());
      setFirst(newLink);
 }

 template<class T>
 void DoublyLinkedList<T>::insertLast(T dd)
 {
      Link<T> *newLink = new Link<T>(dd);
      if(isEmpty())
      {
          setFirst(newLink);
      }
      else
      {
          getLast()->setNext(newLink);
          newLink->setPrevious(getLast());
      }
      setLast(newLink);
 }

 template<class T>
 void DoublyLinkedList<T>::deleteFirst()
 {
      if(isEmpty())
           return;
      Link<T> *temp = getFirst();
      if(getFirst()->getNext() == NULL)
            setLast(NULL);
      else
         getFirst()->getNext()->setPrevious(NULL);
      setFirst(getFirst()->getNext());
      delete temp;
 }

 template<class T>
 void DoublyLinkedList<T>::deleteLast()
 {
      if(isEmpty())
         return;
      Link<T> *temp = getLast();
      if(getFirst()->getNext() == NULL)
             setFirst(NULL);
      else
          getLast()->getPrevious()->setNext(NULL);
      setLast(getLast()->getPrevious());
      delete temp;
 }

 template<class T>
 bool DoublyLinkedList<T>::insertAfter(T key,T dd)
 {
      Link<T> *current = find(key);
      if(current == NULL)
             return false;
      Link<T> *newLink = new Link<T>(dd);
      if(current->getNext() == NULL)
      {
           newLink->setNext(NULL);
           setLast(newLink);
      }
      else
      {
          newLink->setNext(current->getNext());
          current->getNext()->setPrevious(newLink);
      }
      newLink->setPrevious(current);
      current->setNext(newLink);
      return true;
 }

 template<class T>
 void DoublyLinkedList<T>::deleteKey(T key)
 {
      Link<T> *current = find(key);
      if(current==NULL)
           return;
      if(current->getPrevious() == NULL)
             setFirst(current->getNext());
      else
             current->getPrevious()->setNext(current->getNext());
      if(current->getNext() == NULL)
             setLast(current->getPrevious());
      else
             current->getNext()->setPrevious(current->getPrevious());
      delete current;
 }

 template<class T>
 void DoublyLinkedList<T>::displayForward()
 {
      std::cout<<"List (first-->last): ";
      Link<T> *current = getFirst();
      while(current != NULL)
      {
         current->displayLink();
         current = current->getNext();
      }
      std::cout<<"\n";
 }

 template<class T>
 void DoublyLinkedList<T>::displayBackward()
 {
      std::cout<<"List (last-->first): ";
      Link<T> *current = getLast();
      while(current != NULL)
      {
         current->displayLink();
         current = current->getPrevious();
      }
      std::cout<<"\n";
 }

template<class T>
void DoublyLinkedList<T>::concat(DoublyLinkedList<T> &L)
{
     Link<T> *head;
     Link<T> *tail;
     if(!isEmpty() && !L.isEmpty())
     {
          tail = getLast();
          head = L.getFirst();
          tail->setNext(head);
          head->setPrevious(tail);
          setLast(L.getLast());
          L.setFirst(NULL);
          L.setLast(NULL);
     }
     else if(isEmpty())
     {
          setFirst(L.getFirst());
          setLast(L.getLast());
          L.setFirst(NULL);
          L.setLast(NULL);
     }
}

template<class T>
void DoublyLinkedList<T>::enqueue(Link<T> *x)
{
     x->setNext(NULL);
     if(isEmpty())
       setFirst(x);
     else
         getLast()->setNext(x);
     x->setPrevious(getLast());
     setLast(x);
}

template<class T>
Link<T> *DoublyLinkedList<T>::dequeue()
{
        if(isEmpty())
           return NULL;
        Link<T> *temp = getFirst();
        if(getFirst()->getNext() == NULL)
           setLast(NULL);
        else
            getFirst()->getNext()->setPrevious(NULL);
        setFirst(getFirst()->getNext());
        return temp;
}

template<class T>
void DoublyLinkedList<T>::quickSort(int (*Compare)(T,T))
{
     DoublyLinkedList<T> L,E,G;
     Link<T> *pivot;
     Link<T> *temp;
     if(getFirst() != getLast())
     {
         L.setFirst(NULL);L.setLast(NULL);
         E.setFirst(NULL);E.setLast(NULL);
         G.setFirst(NULL);G.setLast(NULL);
         pivot = getLast();
         while(!isEmpty())
         {
             temp = dequeue();
             if(Compare(temp->getData(),pivot->getData()) < 0)
                L.enqueue(temp);
             else if(Compare(temp->getData(),pivot->getData()) == 0)
                E.enqueue(temp);
             else
                G.enqueue(temp);
         }

         L.quickSort(Compare);
         G.quickSort(Compare);

         concat(L);
         concat(E);
         concat(G);
     }
}

int Compare(Point a,Point b)
{
    int t = 1;
    if(a.x < b.x || a.x == b.x && a.y < b.y)
        t = -1;
    if(a.x == b.x && a.y == b.y)
           t = 0;
    return t;
}

int ccw(Point a,Point b,Point c)
{
    return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.y);
}

void Solve(DoublyLinkedList<Point> &A,DoublyLinkedList<Point> &B)
{
     int k,t;
     Link<Point> *pt;
     B.setFirst(NULL);
     B.setLast(NULL);
     if(!A.isEmpty())
     {
        A.quickSort(Compare);
        pt = A.getFirst();
        k = 0;
        while(pt != NULL)
        {
            while(k >= 2 && ccw(B.getLast()->getPrevious()->getData(),B.getLast()->getData(),pt->getData()) <= 0)
            {
                B.deleteLast();
                k--;
            }
            B.insertLast(pt->getData());
            k++;
            pt = pt->getNext();
        }
        t = k + 1;
        pt = A.getLast();
        while(pt != NULL)
        {
            while(k >= t && ccw(B.getLast()->getPrevious()->getData(),B.getLast()->getData(),pt->getData()) <= 0)
            {
                B.deleteLast();
                k--;
            }
            B.insertLast(pt->getData());
            k++;
            pt = pt->getPrevious();
        }
        B.deleteLast();
     }
}

int main(int argc, char *argv[])
{
    DoublyLinkedList<Point> A;
    DoublyLinkedList<Point> B;
    stringstream ss;
    Point p;
    string line;
    int counter;
    while(getline(cin,line))
    {
       ss.clear();
       ss.str(line);
       counter = 1;
       while(ss)
       {
           try
           {
               switch(counter)
               {
                   case 1:
                   {
                       ss>>p.x;
                       break;
                   }
                   case 0:
                   {
                       ss>>p.y;
                       A.insertLast(p);
                       break;
                   }
               }
           }
           catch(...)
           {

           }
           counter = (counter + 1)%2;
       }
        Solve(A,B);
        cout<<"List A \n";
        A.displayForward();
        A.displayBackward();
        cout<<"List B \n";
        B.displayForward();
        B.displayBackward();
        while(!A.isEmpty())
            A.deleteFirst();
        while(!B.isEmpty())
            B.deleteFirst();
    }
    return EXIT_SUCCESS;
}