EntropyIncreaser

Convex Shell [unfinished]

Apr 8th, 2018
192
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.29 KB | None | 0 0
  1. #include <cstdio>
  2.  
  3. #include <algorithm>
  4. #include <functional>
  5. #include <set>
  6.  
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10.  
  11. template <class Num>
  12. struct Point {
  13.     Num x, y;
  14.  
  15.     Point() {}
  16.  
  17.     Point(const Num& x, const Num& y) : x(x), y(y) {}
  18.  
  19.     bool operator<(const Point& p) const {
  20.         if (x != p.x)
  21.             return x < p.x;
  22.         return y < p.y;
  23.     }
  24.  
  25.     Point operator+(const Point& p) const {
  26.         return Point(x + p.x, y + p.y);
  27.     }
  28.  
  29.     Point operator-(const Point& p) const {
  30.         return Point(x - p.x, y - p.y);
  31.     }
  32.  
  33.     Point operator-() const {
  34.         return Point(-x, -y);
  35.     }
  36.  
  37.     Point operator*(const Num& a) const {
  38.         return Point(x * a, y * a);
  39.     }
  40.  
  41.     Point operator/(const Num& a) const {
  42.         return Point(x / a, y / a);
  43.     }
  44.  
  45.     Num operator^(const Point& p) const {
  46.         return x * p.x + y * p.y;
  47.     }
  48.  
  49.     Num operator*(const Point& p) const {
  50.         return x * p.y - y * p.x;
  51.     }
  52.  
  53.     friend Point operator*(const Num& a, const Point& p) {
  54.         return Point(a * p.x, a * p.y);
  55.     }
  56. };
  57.  
  58. template <class Num>
  59. struct ConvexShell {
  60.     typedef Point<Num> PointT;
  61.  
  62.     set<PointT> shell;
  63.  
  64.     void insert(const PointT& p) {
  65.         set<PointT>::iterator it = shell.insert(p).first;
  66.         if (it != shell.begin() && next(it))
  67.     }
  68.  
  69.     PointT bound(const PointT& slope) const;
  70. };
  71.  
  72. ConvexShell<ll> slope;
  73.  
  74. int main() {
  75.     return 0;
  76. }
Advertisement
Add Comment
Please, Sign In to add comment