fork download 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <string>
  4. #include <sstream>
  5.  
  6. using namespace std;
  7.  
  8. struct Point
  9. {
  10.       int x,y;
  11.       friend std::ostream &operator << (std::ostream &output,const Point &p);
  12.       friend std::istream &operator >> (std::istream &input,Point &p);
  13. };
  14.  
  15. bool operator == (Point a,Point b)
  16. {
  17.      return (a.x == b.x && a.y == b.y); 
  18. }
  19.  
  20. bool operator < (Point a,Point b)
  21. {
  22.      return (a.x < b.x || a.x == b.x && a.y < b.y); 
  23. }
  24.  
  25. bool operator > (Point a,Point b)
  26. {
  27.      return !(a < b||a == b); 
  28. }
  29.  
  30.  
  31. std::ostream &operator << (std::ostream &output,const Point &p)
  32. {
  33.         output<<"( "<<p.x<<" , "<<p.y<<" ) ";
  34.         return output;
  35. }
  36.  
  37.  
  38.  
  39. std::istream &operator >> (std::istream &input,Point &p)
  40. {
  41.         input>>p.x>>p.y;; 
  42.         return input;
  43. }
  44.  
  45.  
  46. template<class T>
  47. class Link
  48. {
  49.       private:
  50.               T data;
  51.               Link<T> *next;
  52.               Link<T> *previous;
  53.       public:
  54.              Link(T data);
  55.              void displayLink();
  56.              T getData();
  57.              void setData(T data);
  58.              Link<T> *getNext();
  59.              void setNext(Link<T> *next);
  60.              Link<T> *getPrevious();
  61.              void setPrevious(Link<T> *previous);
  62.              template<class U> friend std::ostream& operator<< (std::ostream& print, Link<U>& obj);
  63.  
  64. };
  65.  
  66. template<class T>
  67. Link<T>::Link(T data)
  68. {
  69.      setData(data);
  70.      setNext(NULL);
  71.      setPrevious(NULL);
  72.  
  73. }
  74.  
  75. template<class T>
  76. void Link<T>::displayLink()
  77. {
  78.      std::cout<<getData()<<" ";
  79. }
  80.  
  81. template<class T>
  82. T Link<T>::getData()
  83. {
  84.      return data;               
  85. }
  86.  
  87. template<class T>
  88. void Link<T>::setData(T data)
  89. {
  90.      this->data = data;               
  91. }
  92.  
  93. template<class T>
  94. Link<T> *Link<T>::getNext()
  95. {
  96.       return next;  
  97. }
  98.  
  99. template<class T>
  100. void Link<T>::setNext(Link<T> *next)
  101. {
  102.       this->next = next; 
  103. }
  104.  
  105. template<class T>
  106. Link<T> *Link<T>::getPrevious()
  107. {
  108.       return previous;  
  109. }
  110.  
  111. template<class T>
  112. void Link<T>::setPrevious(Link<T> *previous)
  113. {
  114.       this->previous = previous; 
  115. }
  116.  
  117.  
  118. template <class U>  
  119. std::ostream& operator<<(std::ostream& print, Link<U> & L)
  120. {
  121.         print << L.getData();
  122.         return print;
  123. }
  124.  
  125. template<class T>
  126. class DoublyLinkedList
  127. {
  128.       private:
  129.               Link<T> *first;
  130.               Link<T> *last;
  131.       public:
  132.              DoublyLinkedList();
  133.              ~DoublyLinkedList();
  134.              Link<T> *getFirst();
  135.              void setFirst(Link<T> *first);
  136.              Link<T> *getLast();
  137.              void setLast(Link<T> *first);
  138.              bool isEmpty();
  139.              Link<T> *find(T key);
  140.              void insertFirst(T dd);
  141.              void insertLast(T dd);
  142.              void insertSorted(T dd);
  143.              void deleteFirst();
  144.              void deleteLast();
  145.              bool insertAfter(T key,T dd);
  146.              void deleteKey(T key);
  147.              void displayForward();
  148.              void displayBackward();
  149. };
  150.  
  151. template<class T>
  152. DoublyLinkedList<T>::DoublyLinkedList()
  153. {
  154.     setFirst(NULL);
  155.     setLast(NULL);                                   
  156. }
  157.  
  158. template<class T>
  159. DoublyLinkedList<T>::~DoublyLinkedList()
  160. {
  161.     while(!isEmpty())
  162.     {
  163.         deleteFirst();             
  164.     }                                   
  165. }
  166.  
  167. template<class T>
  168. Link<T> *DoublyLinkedList<T>::getFirst()
  169. {
  170.        return first; 
  171. }
  172.  
  173. template<class T>
  174. void DoublyLinkedList<T>::setFirst(Link<T> *first)
  175. {
  176.      this->first = first;
  177. }
  178.  
  179. template<class T>
  180. Link<T> *DoublyLinkedList<T>::getLast()
  181. {
  182.        return last; 
  183. }
  184.  
  185. template<class T>
  186. void DoublyLinkedList<T>::setLast(Link<T> *last)
  187. {
  188.      this->last = last;
  189. }
  190.  
  191. template<class T>
  192. bool DoublyLinkedList<T>::isEmpty()
  193. {
  194.      return getFirst()==NULL;
  195. }
  196.  
  197. template<class T>
  198.  Link<T> *DoublyLinkedList<T>::find(T key)
  199.  {
  200.          Link<T> *current = getFirst();
  201.          while(current != NULL && !(current->getData == key))
  202.                current = current->getNext();
  203.          return current;        
  204.  }
  205.  
  206.  template<class T>
  207.  void DoublyLinkedList<T>::insertFirst(T dd)
  208.  {
  209.       Link<T> *newLink = new Link<T>(dd);
  210.       if(isEmpty())
  211.            setLast(newLink);
  212.       else
  213.           getFirst()->setPrevious(newLink);
  214.       newLink->setNext(getFirst());
  215.       setFirst(newLink);        
  216.  }
  217.  
  218.  template<class T>
  219.  void DoublyLinkedList<T>::insertLast(T dd)
  220.  {
  221.       Link<T> *newLink = new Link<T>(dd);
  222.       if(isEmpty())
  223.       {
  224.           setFirst(newLink);         
  225.       }
  226.       else
  227.       {
  228.           getLast()->setNext(newLink);
  229.           newLink->setPrevious(getLast());
  230.       }
  231.       setLast(newLink);
  232.  }
  233.  
  234.  template<class T>
  235.  void DoublyLinkedList<T>::deleteFirst()
  236.  {
  237.       if(isEmpty())
  238.            return;
  239.       Link<T> *temp = getFirst();
  240.       if(getFirst()->getNext() == NULL)
  241.             setLast(NULL);
  242.       else
  243.          getFirst()->getNext()->setPrevious(NULL);
  244.       setFirst(getFirst()->getNext());
  245.       delete temp;                            
  246.  }
  247.  
  248.  template<class T> 
  249.  void DoublyLinkedList<T>::deleteLast()
  250.  {
  251.       if(isEmpty())
  252.          return;
  253.       Link<T> *temp = getLast();
  254.       if(getFirst()->getNext() == NULL)
  255.              setFirst(NULL);
  256.       else
  257.           getLast()->getPrevious()->setNext(NULL);
  258.       setLast(getLast()->getPrevious());
  259.       delete temp;                  
  260.  }
  261.  
  262.  template<class T>
  263.  bool DoublyLinkedList<T>::insertAfter(T key,T dd)
  264.  {
  265.       Link<T> *current = find(key);
  266.       if(current == NULL)
  267.              return false;
  268.       Link<T> *newLink = new Link<T>(dd); 
  269.       if(current->getNext() == NULL)
  270.       {
  271.            newLink->setNext(NULL);
  272.            setLast(newLink);                 
  273.       }
  274.       else
  275.       {
  276.           newLink->setNext(current->getNext());
  277.           current->getNext()->setPrevious(newLink);
  278.       }
  279.       newLink->setPrevious(current);
  280.       current->setNext(newLink);
  281.       return true;    
  282.  }
  283.  
  284.  template<class T>
  285.  void DoublyLinkedList<T>::insertSorted(T key)
  286.  {
  287.       Link<T> *newLink = new Link<T>(key);
  288.       Link<T> *previous = NULL;
  289.       Link<T> *current = getFirst();
  290.  
  291.       while(current != NULL && key > current->getData())
  292.       {
  293.             previous = current;
  294.             current = current->getNext();        
  295.       }
  296.       if(previous == NULL)
  297.           setFirst(newLink);
  298.       else
  299.           previous->setNext(newLink);
  300.       newLink->setNext(current);
  301.       if(current == NULL)
  302.           setLast(newLink);
  303.       else
  304.           current->setPrevious(newLink);
  305.       newLink->setPrevious(previous);                
  306.  }
  307.  
  308.  template<class T>
  309.  void DoublyLinkedList<T>::deleteKey(T key)
  310.  {
  311.       Link<T> *current = find(key);
  312.       if(current==NULL)
  313.            return;
  314.       if(current->getPrevious() == NULL)
  315.              setFirst(current->getNext());
  316.       else
  317.              current->getPrevious()->setNext(current->getNext());
  318.       if(current->getNext() == NULL)
  319.              setLast(current->getPrevious());
  320.       else
  321.              current->getNext()->setPrevious(current->getPrevious());
  322.       delete current;
  323.  }
  324.  
  325.  template<class T>
  326.  void DoublyLinkedList<T>::displayForward()
  327.  {
  328.       std::cout<<"List (first-->last): ";
  329.       Link<T> *current = getFirst();
  330.       while(current != NULL)
  331.       {
  332.          current->displayLink();
  333.          current = current->getNext();   
  334.       }
  335.       std::cout<<"\n";
  336.  }
  337.  
  338.  template<class T>
  339.  void DoublyLinkedList<T>::displayBackward()
  340.  {
  341.       std::cout<<"List (last-->first): ";
  342.       Link<T> *current = getLast();
  343.       while(current != NULL)
  344.       {
  345.          current->displayLink();
  346.          current = current->getPrevious();   
  347.       }
  348.       std::cout<<"\n";
  349.  }
  350.  
  351.  
  352.  
  353. int vect(Point a1,Point a2,Point b1,Point b2)
  354. {
  355.     return (a2.x - a1.x)*(b2.y - b1.y) - (b2.x - b1.x)*(a2.y - a1.y);
  356. }
  357.  
  358. int dist2(Point a1,Point a2)
  359. {
  360.     return (a2.x - a1.x)*(a2.x - a1.x) + (a2.y - a1.y)*(a2.y - a1.y);
  361. }
  362.  
  363. void Jarvis(DoublyLinkedList<Point> &A,DoublyLinkedList<Point> &B)
  364. {
  365.      Link<Point> *p,*q,*m,*min;
  366.      if(!A.isEmpty())
  367.      {
  368.          m = A.getFirst();
  369.          p = m->getNext();
  370.          while(p != NULL)
  371.          {
  372.               if(p->getData().y < m->getData().y)   
  373.                   m = p;
  374.               else if(p->getData().y == m->getData().y && p->getData().x > m->getData().x)              
  375.                    m = p;
  376.               p = p->getNext();
  377.          }
  378.  
  379.          if(m->getPrevious() == NULL)
  380.               A.setFirst(m->getNext());
  381.          else
  382.              m->getPrevious()->setNext(m->getNext());
  383.          if(m->getNext() == NULL)
  384.             A.setLast(m->getPrevious());
  385.          else
  386.              m->getNext()->setPrevious(m->getPrevious());
  387.  
  388.          if(A.isEmpty())
  389.             A.setLast(m);
  390.          else
  391.              A.getFirst()->setPrevious(m);
  392.          m->setNext(A.getFirst());
  393.          m->setPrevious(NULL);
  394.          A.setFirst(m);
  395.  
  396.          B.insertLast(A.getFirst()->getData());
  397.  
  398.          min = A.getFirst()->getNext();
  399.  
  400.          do
  401.          {
  402.              q = A.getFirst()->getNext();
  403.              while(q != NULL)
  404.              {
  405.                  if((vect(B.getLast()->getData(),min->getData(),B.getLast()->getData(),q->getData()) < 0)||
  406.                  (vect(B.getLast()->getData(),min->getData(),B.getLast()->getData(),q->getData()) == 0)&&
  407.                  (dist2(B.getLast()->getData(),min->getData()) < dist2(B.getLast()->getData(),q->getData())))
  408.                     min = q;
  409.                  q = q->getNext();    
  410.              }
  411.              B.insertLast(min->getData());
  412.              min = A.getFirst();
  413.          }
  414.          while(!(B.getLast()->getData() == B.getFirst()->getData()));
  415.          B.deleteLast();
  416.      }
  417. }
  418.  
  419. int main(int argc, char *argv[])
  420. {
  421.     DoublyLinkedList<Point> A;
  422.     DoublyLinkedList<Point> B;
  423.     stringstream ss;
  424.     Point p;
  425.     string line;
  426.     int counter;
  427.     while(getline(cin,line))
  428.     {
  429.        ss.clear();
  430.        ss.str(line);
  431.        counter = 1;
  432.        while(ss)
  433.        {
  434.            try
  435.            {
  436.                switch(counter)
  437.                {
  438.                    case 1:
  439.                    {
  440.                        ss>>p.x;
  441.                        break;
  442.                    }
  443.                    case 0:
  444.                    {
  445.                        ss>>p.y;
  446.                        A.insertSorted(p);
  447.                        break;
  448.                    }
  449.                }
  450.            }
  451.            catch(...)
  452.            {
  453.  
  454.            }
  455.            counter = (counter + 1)%2;
  456.        }
  457.         //Jarvis(A,B);
  458.         cout<<"List A \n";
  459.         A.displayForward();
  460.         A.displayBackward();
  461.        /* cout<<"List B \n";
  462.         B.displayForward();
  463.         B.displayBackward(); */
  464.         while(!A.isEmpty())
  465.             A.deleteFirst();
  466.         while(!B.isEmpty())
  467.             B.deleteFirst();
  468.     }    
  469.     return EXIT_SUCCESS;
  470. }
  471.  
Success #stdin #stdout 0s 4512KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/wnfIov
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!