fork download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <iterator>
  4. #include <ostream>
  5. #include <cassert>
  6. #include <vector>
  7. #include <deque>
  8. #include <array>
  9.  
  10. using namespace std;
  11.  
  12. template<typename Iterator>
  13. using value_type = typename iterator_traits<Iterator>::value_type;
  14.  
  15. typedef double Coord;
  16. typedef array<Coord,2> Point;
  17.  
  18. auto cross=[](Point o,Point a,Point b)
  19. {
  20.     return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0]);
  21. };
  22.  
  23. template<typename RanIt,typename InIt>
  24. RanIt monotone_chain(InIt first_point,InIt last_point, RanIt first,RanIt last)
  25. {
  26.     while(first_point!=last_point)
  27.     {
  28.         while
  29.         (
  30.             (last-first)>=2 &&
  31.             cross(last[-2], last[-1], *first_point)<=0
  32.         )
  33.             --last;
  34.         *last++ = *first_point++;
  35.     }
  36.     return last;
  37. }
  38.  
  39. template<typename RanItIn,typename RanItOut>
  40. RanItOut convex_hull(RanItIn first_point,RanItIn last_point, RanItOut first)
  41. {
  42.     typedef reverse_iterator<RanItIn> RevIn;
  43.     if(first_point==last_point)
  44.         return first;
  45.     sort(first_point,last_point);
  46.     first = monotone_chain(first_point,last_point, first,first);
  47.     --first;
  48.     return monotone_chain(RevIn(last_point),RevIn(first_point), first,first);
  49. }
  50.  
  51. template<typename RanIt>
  52. vector<value_type<RanIt>> convex_hull(RanIt first_point,RanIt last_point)
  53. {
  54.     vector<value_type<RanIt>> result(2*distance(first_point,last_point));
  55.     result.erase
  56.     (
  57.         convex_hull(first_point,last_point,begin(result)),
  58.         end(result)
  59.     );
  60.     return result;
  61. }
  62.  
  63. ostream &operator<<(ostream &os,Point p)
  64. {
  65.     return os << "(" << p[0] << "," << p[1] << ")";
  66. }
  67.  
  68. int main()
  69. {
  70.     deque<Point> input;
  71.     for(Coord i=0;i<10;++i) for(Coord j=0;j<10;++j)
  72.         input.push_front(Point{{i,j}});
  73.     for(auto p : convex_hull(begin(input),end(input)))
  74.         cout << p << endl;
  75. }
Success #stdin #stdout 0s 3040KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(0,0)
(9,0)
(9,9)
(0,9)
(0,0)
https://ideone.com/qLBGne
language:
C++14 (gcc 8.3)
created:
12 years ago
visibility:
secret

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!