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