-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathconvexhull.cpp
More file actions
65 lines (53 loc) · 1.28 KB
/
convexhull.cpp
File metadata and controls
65 lines (53 loc) · 1.28 KB
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
/*
In the name of ALLAH
Author : Raashid Anwar
*/
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
const int M1 = 998244353;
const int M2 = 1000000007;
mt19937 rng((uint64_t)chrono::steady_clock::now().time_since_epoch().count());
struct point {
int x, y;
point(int _x, int _y) : x(_x), y(_y) {}
};
class convexhull {
vector <point> hull;
public :
convexhull() {
hull.clear();
}
bool is_bad(point a, point b, point c) {
return double(b.y - c.y) / double((a.y - b.y)) <= double(c.x - b.x) / double(b.x - a. x);
}
void addline(int x, int y) {
point p = {x, y};
while ((int)hull.size() > 1 && is_bad(hull[(int)hull.size() - 2], hull.back(), p))
hull.pop_back();
hull.push_back(p);
}
int get_max(int x) {
point p = {x, 1};
int lo = -1, hi = (int)hull.size() - 1;
while (hi - lo > 1) {
int mi = (lo + hi) >> 1;
if (x * hull[mi].x + hull[mi].y <= x * hull[mi + 1].x + hull[mi + 1].y) {
lo = mi;
} else {
hi = mi;
}
}
return (x * hull[hi].x + hull[hi].y);
}
void clear() {
hull.clear();
}
};
void solve() {
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
}