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