fork(2) download
copy 
  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.              void setFirst(Link<T> *first);
  125.              Link<T> *getLast();
  126.              void setLast(Link<T> *first);
  127.              bool isEmpty();
  128.              Link<T> *find(T key);
  129.              void insertFirst(T dd);
  130.              void insertLast(T dd);
  131.              void deleteFirst();
  132.              void deleteLast();
  133.              bool insertAfter(T key,T dd);
  134.              void deleteKey(T key);
  135.              void displayForward();
  136.              void displayBackward();
  137. };
  138.  
  139. template<class T>
  140. DoublyLinkedList<T>::DoublyLinkedList()
  141. {
  142.     setFirst(NULL);
  143.     setLast(NULL);                                   
  144. }
  145.  
  146. template<class T>
  147. DoublyLinkedList<T>::~DoublyLinkedList()
  148. {
  149.     while(!isEmpty())
  150.     {
  151.         deleteFirst();             
  152.     }                                   
  153. }
  154.  
  155. template<class T>
  156. Link<T> *DoublyLinkedList<T>::getFirst()
  157. {
  158.        return first; 
  159. }
  160.  
  161. template<class T>
  162. void DoublyLinkedList<T>::setFirst(Link<T> *first)
  163. {
  164.      this->first = first;
  165. }
  166.  
  167. template<class T>
  168. Link<T> *DoublyLinkedList<T>::getLast()
  169. {
  170.        return last; 
  171. }
  172.  
  173. template<class T>
  174. void DoublyLinkedList<T>::setLast(Link<T> *last)
  175. {
  176.      this->last = last;
  177. }
  178.  
  179. template<class T>
  180. bool DoublyLinkedList<T>::isEmpty()
  181. {
  182.      return getFirst()==NULL;
  183. }
  184.  
  185. template<class T>
  186.  Link<T> *DoublyLinkedList<T>::find(T key)
  187.  {
  188.          Link<T> *current = getFirst();
  189.          while(current != NULL && !(current->getData == key))
  190.                current = current->getNext();
  191.          return current;        
  192.  }
  193.  
  194.  template<class T>
  195.  void DoublyLinkedList<T>::insertFirst(T dd)
  196.  {
  197.       Link<T> *newLink = new Link<T>(dd);
  198.       if(isEmpty())
  199.            setLast(newLink);
  200.       else
  201.           getFirst()->setPrevious(newLink);
  202.       newLink->setNext(getFirst());
  203.       setFirst(newLink);        
  204.  }
  205.  
  206.  template<class T>
  207.  void DoublyLinkedList<T>::insertLast(T dd)
  208.  {
  209.       Link<T> *newLink = new Link<T>(dd);
  210.       if(isEmpty())
  211.       {
  212.           setFirst(newLink);         
  213.       }
  214.       else
  215.       {
  216.           getLast()->setNext(newLink);
  217.           newLink->setPrevious(getLast());
  218.       }
  219.       setLast(newLink);
  220.  }
  221.  
  222.  template<class T>
  223.  void DoublyLinkedList<T>::deleteFirst()
  224.  {
  225.       if(isEmpty())
  226.            return;
  227.       Link<T> *temp = getFirst();
  228.       if(getFirst()->getNext() == NULL)
  229.             setLast(NULL);
  230.       else
  231.          getFirst()->getNext()->setPrevious(NULL);
  232.       setFirst(getFirst()->getNext());
  233.       delete temp;                            
  234.  }
  235.  
  236.  template<class T> 
  237.  void DoublyLinkedList<T>::deleteLast()
  238.  {
  239.       if(isEmpty())
  240.          return;
  241.       Link<T> *temp = getLast();
  242.       if(getFirst()->getNext() == NULL)
  243.              setFirst(NULL);
  244.       else
  245.           getLast()->getPrevious()->setNext(NULL);
  246.       setLast(getLast()->getPrevious());
  247.       delete temp;                  
  248.  }
  249.  
  250.  template<class T>
  251.  bool DoublyLinkedList<T>::insertAfter(T key,T dd)
  252.  {
  253.       Link<T> *current = find(key);
  254.       if(current == NULL)
  255.              return false;
  256.       Link<T> *newLink = new Link<T>(dd); 
  257.       if(current->getNext() == NULL)
  258.       {
  259.            newLink->setNext(NULL);
  260.            setLast(newLink);                 
  261.       }
  262.       else
  263.       {
  264.           newLink->setNext(current->getNext());
  265.           current->getNext()->setPrevious(newLink);
  266.       }
  267.       newLink->setPrevious(current);
  268.       current->setNext(newLink);
  269.       return true;    
  270.  }
  271.  
  272.  template<class T>
  273.  void DoublyLinkedList<T>::deleteKey(T key)
  274.  {
  275.       Link<T> *current = find(key);
  276.       if(current==NULL)
  277.            return;
  278.       if(current->getPrevious() == NULL)
  279.              setFirst(current->getNext());
  280.       else
  281.              current->getPrevious()->setNext(current->getNext());
  282.       if(current->getNext() == NULL)
  283.              setLast(current->getPrevious());
  284.       else
  285.              current->getNext()->setPrevious(current->getPrevious());
  286.       delete current;
  287.  }
  288.  
  289.  template<class T>
  290.  void DoublyLinkedList<T>::displayForward()
  291.  {
  292.       std::cout<<"List (first-->last): ";
  293.       Link<T> *current = getFirst();
  294.       while(current != NULL)
  295.       {
  296.          current->displayLink();
  297.          current = current->getNext();   
  298.       }
  299.       std::cout<<"\n";
  300.  }
  301.  
  302.  template<class T>
  303.  void DoublyLinkedList<T>::displayBackward()
  304.  {
  305.       std::cout<<"List (last-->first): ";
  306.       Link<T> *current = getLast();
  307.       while(current != NULL)
  308.       {
  309.          current->displayLink();
  310.          current = current->getPrevious();   
  311.       }
  312.       std::cout<<"\n";
  313.  }
  314.  
  315. int ScaledDistance(Point u,Point v,Point p)
  316. {
  317.     return (p.x - v.x) * (u.y - v.y) - (p.y - v.y) * (u.x - v.x);
  318. }
  319.  
  320. int Direction(Point u,Point v, Point p)
  321. {
  322.     return (p.x - v.x) * (u.y - v.y) - (p.y - v.y) * (u.x - v.x);
  323. }
  324.  
  325. int Projection(Point u,Point v,Point p)
  326. {
  327.     return (p.x - v.x) * (u.x - v.x) + (p.y - v.y) *(u.y - v.y);
  328. }
  329.  
  330. void Select(Point &p,Point &q, DoublyLinkedList<Point> S)
  331. {
  332.     Point pt;
  333.     Link<Point> *element = S.getFirst();
  334.     q = element->getData();
  335.     p = q;
  336.     element = element->getNext();
  337.     while(element != NULL)
  338.     {
  339.         pt = element->getData();
  340.         if((pt.y < q.y) || (pt.y == q.y && pt.x < q.x)) q = pt;
  341.         if((pt.y > p.y) || (pt.y == p.y && pt.x > p.x)) p = pt;
  342.         element = element->getNext();
  343.     }
  344. }
  345.  
  346. void Split(Point p, Point q, DoublyLinkedList<Point> &S, DoublyLinkedList<Point> &R, DoublyLinkedList<Point> &L)
  347. {
  348.     int dir;
  349.     Point pt;
  350.     while(!S.isEmpty())
  351.     {
  352.         pt = S.getFirst()->getData();
  353.         S.deleteFirst();
  354.         dir = Direction(p,q,pt);
  355.         if(dir > 0) R.insertLast(pt);
  356.         if(dir < 0) L.insertLast(pt);
  357.     }
  358. }
  359.  
  360. void PruneAndSplit(Point p, Point q,Point r, DoublyLinkedList<Point> &S, DoublyLinkedList<Point> &U, DoublyLinkedList<Point> &L)
  361. {
  362.     DoublyLinkedList<Point> internal1,internal2;
  363.     Split(p,r,S,U,internal1);
  364.     Split(r,q,internal1,L,internal2);
  365.     while(!internal2.isEmpty())
  366.         internal2.deleteFirst();
  367. }
  368.  
  369. Point FarthestPoint(Point p,Point q,DoublyLinkedList<Point> S)
  370. {
  371.     int maxdist,dist;
  372.     Point r,pt;
  373.     maxdist = 0;
  374.     Link<Point> *element = S.getFirst();
  375.     while(element != NULL)
  376.     {
  377.         pt = element->getData();
  378.         dist = ScaledDistance(p,q,pt);
  379.         if(dist > maxdist)
  380.         {
  381.             maxdist = dist;
  382.             r = pt;
  383.         }
  384.         else if(dist == maxdist)
  385.         {
  386.             if(Projection(p,q,pt) > Projection(p,q,r))
  387.             {
  388.                 maxdist = dist;
  389.                 r = pt;
  390.             }
  391.         }
  392.         element = element->getNext();
  393.  
  394.     }
  395.     return r;
  396. }
  397.  
  398. void QuickHull(Point p,Point q,DoublyLinkedList<Point> &S,DoublyLinkedList<Point> &CH)
  399. {
  400.     Point r;
  401.     DoublyLinkedList<Point> U,L;
  402.     if(!S.isEmpty())
  403.     {
  404.         r = FarthestPoint(p,q,S);
  405.         PruneAndSplit(p,q,r,S,U,L);
  406.         QuickHull(p,r,U,CH);
  407.         CH.insertLast(r);
  408.         QuickHull(r,q,L,CH);
  409.     }
  410. }
  411.  
  412. void Solve(DoublyLinkedList<Point> &A,DoublyLinkedList<Point> &CH)
  413. {
  414.     DoublyLinkedList<Point> S,L,R;
  415.     Point p,q;
  416.     Link<Point> *element = A.getFirst();
  417.     while(element != NULL)
  418.     {
  419.         S.insertLast(element->getData());
  420.         element = element->getNext();
  421.     }
  422.     Select(p,q,S);
  423.     Split(p,q,S,R,L);
  424.     CH.insertLast(p);
  425.     QuickHull(p,q,R,CH);
  426.     CH.insertLast(q);
  427.     QuickHull(q,p,L,CH);
  428. }
  429.  
  430. int main(int argc, char *argv[])
  431. {
  432.     DoublyLinkedList<Point> A;
  433.     DoublyLinkedList<Point> B;
  434.     stringstream ss;
  435.     Point p;
  436.     string line;
  437.     int counter;
  438.     while(getline(cin,line))
  439.     {
  440.        ss.clear();
  441.        ss.str(line);
  442.        counter = 1;
  443.        while(ss)
  444.        {
  445.            try
  446.            {
  447.                switch(counter)
  448.                {
  449.                    case 1:
  450.                    {
  451.                        ss>>p.x;
  452.                        break;
  453.                    }
  454.                    case 0:
  455.                    {
  456.                        ss>>p.y;
  457.                        A.insertLast(p);
  458.                        break;
  459.                    }
  460.                }
  461.            }
  462.            catch(...)
  463.            {
  464.  
  465.            }
  466.            counter = (counter + 1)%2;
  467.        }
  468.         Solve(A,B);
  469.         cout<<"List A \n";
  470.         A.displayForward();
  471.         A.displayBackward();
  472.         cout<<"List B \n";
  473.         B.displayForward();
  474.         B.displayBackward();
  475.         while(!A.isEmpty())
  476.             A.deleteFirst();
  477.         while(!B.isEmpty())
  478.             B.deleteFirst();
  479.     }    
  480.     return EXIT_SUCCESS;
  481. }
  482.  
Runtime error #stdin #stdout #stderr 0s 80768KB
comments (?)
stdin
copy 
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
copy 
Standard output is empty
stderr
copy 
*** Error in `./prog': double free or corruption (fasttop): 0x0000562816488a50 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x70bcb)[0x2adbf9f0ebcb]
/lib/x86_64-linux-gnu/libc.so.6(+0x76f96)[0x2adbf9f14f96]
/lib/x86_64-linux-gnu/libc.so.6(+0x7778e)[0x2adbf9f1578e]
./prog(+0x16cf)[0x5628152366cf]
./prog(+0x1a69)[0x562815236a69]
./prog(+0x10fa)[0x5628152360fa]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf1)[0x2adbf9ebe2b1]
./prog(+0x130a)[0x56281523630a]
======= Memory map: ========
2adbf91be000-2adbf91e1000 r-xp 00000000 fd:00 2840974                    /lib/x86_64-linux-gnu/ld-2.24.so
2adbf91e1000-2adbf91e5000 rw-p 00000000 00:00 0 
2adbf91ee000-2adbf91f3000 rw-p 00000000 00:00 0 
2adbf93e1000-2adbf93e2000 r--p 00023000 fd:00 2840974                    /lib/x86_64-linux-gnu/ld-2.24.so
2adbf93e2000-2adbf93e3000 rw-p 00024000 fd:00 2840974                    /lib/x86_64-linux-gnu/ld-2.24.so
2adbf93e3000-2adbf93e4000 rw-p 00000000 00:00 0 
2adbf93e4000-2adbf9556000 r-xp 00000000 fd:00 2967755                    /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.22
2adbf9556000-2adbf9756000 ---p 00172000 fd:00 2967755                    /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.22
2adbf9756000-2adbf9760000 r--p 00172000 fd:00 2967755                    /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.22
2adbf9760000-2adbf9762000 rw-p 0017c000 fd:00 2967755                    /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.22
2adbf9762000-2adbf9766000 rw-p 00000000 00:00 0 
2adbf9766000-2adbf9869000 r-xp 00000000 fd:00 2841003                    /lib/x86_64-linux-gnu/libm-2.24.so
2adbf9869000-2adbf9a68000 ---p 00103000 fd:00 2841003                    /lib/x86_64-linux-gnu/libm-2.24.so
2adbf9a68000-2adbf9a69000 r--p 00102000 fd:00 2841003                    /lib/x86_64-linux-gnu/libm-2.24.so
2adbf9a69000-2adbf9a6a000 rw-p 00103000 fd:00 2841003                    /lib/x86_64-linux-gnu/libm-2.24.so
2adbf9a6a000-2adbf9a80000 r-xp 00000000 fd:00 2840941                    /lib/x86_64-linux-gnu/libgcc_s.so.1
2adbf9a80000-2adbf9c7f000 ---p 00016000 fd:00 2840941                    /lib/x86_64-linux-gnu/libgcc_s.so.1
2adbf9c7f000-2adbf9c80000 r--p 00015000 fd:00 2840941                    /lib/x86_64-linux-gnu/libgcc_s.so.1
2adbf9c80000-2adbf9c81000 rw-p 00016000 fd:00 2840941                    /lib/x86_64-linux-gnu/libgcc_s.so.1
2adbf9c81000-2adbf9c99000 r-xp 00000000 fd:00 2840960                    /lib/x86_64-linux-gnu/libpthread-2.24.so
2adbf9c99000-2adbf9e98000 ---p 00018000 fd:00 2840960                    /lib/x86_64-linux-gnu/libpthread-2.24.so
2adbf9e98000-2adbf9e99000 r--p 00017000 fd:00 2840960                    /lib/x86_64-linux-gnu/libpthread-2.24.so
2adbf9e99000-2adbf9e9a000 rw-p 00018000 fd:00 2840960                    /lib/x86_64-linux-gnu/libpthread-2.24.so
2adbf9e9a000-2adbf9e9e000 rw-p 00000000 00:00 0 
2adbf9e9e000-2adbfa033000 r-xp 00000000 fd:00 2841097                    /lib/x86_64-linux-gnu/libc-2.24.so
2adbfa033000-2adbfa232000 ---p 00195000 fd:00 2841097                    /lib/x86_64-linux-gnu/libc-2.24.so
2adbfa232000-2adbfa236000 r--p 00194000 fd:00 2841097                    /lib/x86_64-linux-gnu/libc-2.24.so
2adbfa236000-2adbfa238000 rw-p 00198000 fd:00 2841097                    /lib/x86_64-linux-gnu/libc-2.24.so
2adbfa238000-2adbfa23c000 rw-p 00000000 00:00 0 
2adbfc000000-2adbfc021000 rw-p 00000000 00:00 0 
2adbfc021000-2adc00000000 ---p 00000000 00:00 0 
562815235000-562815238000 r-xp 00000000 fd:00 30320642                   /home/vN4Lr3/prog
562815437000-562815438000 r--p 00002000 fd:00 30320642                   /home/vN4Lr3/prog
562815438000-562815439000 rw-p 00003000 fd:00 30320642                   /home/vN4Lr3/prog
562816475000-5628164a7000 rw-p 00000000 00:00 0                          [heap]
7fff479ca000-7fff479eb000 rw-p 00000000 00:00 0                          [stack]
7fff479f0000-7fff479f2000 r-xp 00000000 00:00 0                          [vdso]
7fff479f2000-7fff479f4000 r--p 00000000 00:00 0                          [vvar]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
https://ideone.com/bO8MMo
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!