Competitive_Programming/Geometry/dynamic_ch.cpp at master · jonh14lk/Competitive_Programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long int
#define endl '\n'
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pi>
#define fir first
#define sec second
#define MAXN 100005
#define double long double
#define mod 1000000007

const double eps = 1e-9;

struct pt
{
  double x, y;
  pt operator-(pt p) { return {x - p.x, y - p.y}; }
  bool eq(double a, double b) const
  {
    return abs(a - b) <= eps;
  }
  double operator^(const pt p) const { return x * p.y - y * p.x; }
  bool operator<(const pt p) const
  {
    if (!eq(x, p.x))
      return x < p.x;
    if (!eq(y, p.y))
      return y < p.y;
    return 0;
  }
  bool operator==(const pt p) const
  {
    return eq(x, p.x) and eq(y, p.y);
  }
};
double sarea(pt p, pt q, pt r)
{
  return ((q - p) ^ (r - q)) / 2;
}
bool ccw(pt p, pt q, pt r)
{
  return sarea(p, q, r) > eps;
}
// https://github.com/brunomaletta/Biblioteca/blob/master/Codigo/Problemas/dynamicHull.cpp
struct upper
{
  set<pt> se;
  set<pt>::iterator it;
  // 0 - fora
  // 1 - dentro
  // 2 - na borda
  int is_under(pt p)
  {
    it = se.lower_bound(p);
    if (it == se.end())
      return 0;
    if (it == se.begin())
      return p == *it ? 2 : 0;
    if (ccw(p, *it, *prev(it)))
      return 1;
    return ccw(p, *prev(it), *it) ? 0 : 2;
  }
  void insert(pt p)
  {
    if (is_under(p))
      return;
    if (it != se.end())
      while (next(it) != se.end() and !ccw(*next(it), *it, p))
        it = se.erase(it);
    if (it != se.begin())
      while (--it != se.begin() and !ccw(p, *it, *prev(it)))
        it = se.erase(it);
    se.insert(p);
  }
};
struct dyn_hull
{
  upper U, L;
  int is_inside(pt p)
  {
    int u = U.is_under(p), l = L.is_under({-p.x, -p.y});
    if (!u || !l)
      return 0;
    return max(u, l);
  }
  void insert(pt p)
  {
    U.insert(p);
    L.insert({-p.x, -p.y});
  }
  int size()
  {
    int ans = U.se.size() + L.se.size();
    return ans <= 2 ? ans / 2 : ans - 2;
  }
};
signed main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  return 0;
}
// convex hull dinamico
// problema para usar: https://open.kattis.com/problems/hiringhelp