@[阿尔托莉雅丶](/user/105820) 线性查找肯定不行啊，有 $\log$ 做法为什么不用呢
```cpp
template <typename _Tp>
struct point {
_Tp x, y;
inline point(const _Tp& xx, const _Tp& yy) : x(xx), y(yy) {}
inline point() {}
inline point(const std::pair<_Tp, _Tp>& pr) : x(pr.first), y(pr.second) {}
inline point<_Tp>& operator=(const point<_Tp>& p) {
x = p.x;
y = p.y;
return *this;
}
inline bool operator==(const point<_Tp>& o) const { return x == o.x && y == o.y; }
friend inline double dist(const point<_Tp>& a, const point<_Tp>& b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); }
friend inline _Tp dist_sqr(const point<_Tp>& a, const point<_Tp>& b) { return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); }
inline _Tp dist_sqr() const { return x * x + y * y; }
inline point<_Tp> operator+(const point<_Tp>& p) const { return point<_Tp>(x + p.x, y + p.y); }
inline point<_Tp> operator-(const point<_Tp>& p) const { return point<_Tp>(x - p.x, y - p.y); }
inline _Tp operator*(const point<_Tp>& p) const { return x * p.y - y * p.x; }
template <typename _Istream>
friend inline _Istream& operator>>(_Istream& is, point<_Tp>& p) { return is >> p.x >> p.y; }
operator std::pair<_Tp, _Tp>() const { return std::make_pair(x, y); }
};
template <typename _Tp, typename _Alloc = std::allocator<_Tp> >
class convex_hull {
public:
typedef point<_Tp> value_type;
typedef const point<_Tp>& reference;
typedef const point<_Tp>& const_reference;
typedef const point<_Tp>* pointer;
typedef const point<_Tp>* const_pointer;
typedef typename std::allocator_traits<_Alloc>::template rebind_alloc<point<_Tp> > allocator_type;
typedef typename std::vector<point<_Tp>, allocator_type>::size_type size_type;
typedef typename std::vector<point<_Tp>, allocator_type>::difference_type difference_type;
typedef typename std::vector<point<_Tp>, allocator_type>::const_iterator iterator;
typedef typename std::vector<point<_Tp>, allocator_type>::const_iterator const_iterator;
typedef typename std::vector<point<_Tp>, allocator_type>::const_reverse_iterator reverse_iterator;
typedef typename std::vector<point<_Tp>, allocator_type>::const_reverse_iterator const_reverse_iterator;
private:
typedef std::less<_Tp> _Comp;
std::vector<point<_Tp>, allocator_type> _M_vec;
static inline _Comp _M_comp{};
static constexpr double _S_eps = 1e-5;
public:
static inline bool cmp1(const point<_Tp>& a, const point<_Tp>& b) { return a.y == b.y ? _M_comp(a.x, b.x) : _M_comp(a.y, b.y); }
static inline bool cmp2(const point<_Tp>& a, const point<_Tp>& b) { return _M_comp(_Tp(), a * b) || (!_M_comp(a * b, _Tp()) && _M_comp(a.dist_sqr(), b.dist_sqr())); }
static inline int _S_sign(double v) { return v < -_S_eps ? -1 : (_S_eps < v ? 1 : 0); }
private:
template <typename _O_alloc>
static inline void _S_convex(std::vector<point<_Tp>, _O_alloc>& vec) {
const size_t n = vec.size();
if (n <= 2) return;
std::sort(vec.begin(), vec.end(), cmp1);
std::vector<size_t, typename std::allocator_traits<_Alloc>::template rebind_alloc<size_t> > stk;
point<_Tp> p = vec[0];
for (size_t i = 0; i < n; i++) vec[i] = vec[i] - p;
auto tmp = vec.begin();
std::sort(++tmp, vec.end(), cmp2);
size_t top = 0;
stk.resize(n + 1);
stk[++top] = 0;
for (int i = 1; i < n; i++) {
while (top > 1 && !_M_comp((vec[i] - vec[stk[top - 1]]) * (vec[stk[top]] - vec[stk[top - 1]]), _Tp())) --top;
stk[++top] = i;
}
std::vector<point<_Tp>, _O_alloc> ret;
for (size_t i = 1; i <= top; i++) ret.push_back(vec[stk[i]] + p);
vec = ret;
}
template <typename _O_alloc>
static inline _Tp _S_diameter(const std::vector<point<_Tp>, _O_alloc>& vec) {
const size_t n = vec.size();
_Tp ans = (vec[1] - vec[0]).dist_sqr();
if (n == 2) return ans;
for (size_t i = 0, j = 2; i < n; i++) {
while (_S_sign(fabs((double)((vec[(i + 1) % n] - vec[i]) * (vec[j] - vec[i]))) - fabs((double)((vec[(i + 1) % n] - vec[i]) * (vec[(j + 1) % n] - vec[i])))) < 0) j = (j + 1) % n;
ans = std::max(ans, std::max((vec[j] - vec[i]).dist_sqr(), (vec[j] - vec[(i + 1) % n]).dist_sqr(), _M_comp), _M_comp);
}
return ans;
}
public:
inline convex_hull() = default;
inline convex_hull(const std::vector<point<_Tp>, allocator_type>& vec) : _M_vec(vec) { _S_convex(_M_vec); }
inline operator std::vector<point<_Tp>, allocator_type>() const { return _M_vec; }
inline iterator begin() { return _M_vec.begin(); }
inline iterator end() { return _M_vec.end(); }
inline const_iterator begin() const { return _M_vec.begin(); }
inline const_iterator end() const { return _M_vec.end(); }
inline const_iterator cbegin() const { return _M_vec.cbegin(); }
inline const_iterator cend() const { return _M_vec.cend(); }
inline reverse_iterator rbegin() { return _M_vec.rbegin(); }
inline reverse_iterator rend() { return _M_vec.rend(); }
inline const_reverse_iterator rbegin() const { return _M_vec.rbegin(); }
inline const_reverse_iterator rend() const { return _M_vec.rend(); }
inline const_reverse_iterator crbegin() const { return _M_vec.crbegin(); }
inline const_reverse_iterator crend() const { return _M_vec.crend(); }
inline point<_Tp>* data() { return _M_vec.data(); }
inline const point<_Tp>* data() const { return _M_vec.data(); }
inline size_type size() const { return _M_vec.size(); }
inline bool empty() const { return _M_vec.empty(); }
inline void clear() { _M_vec.clear(); }
inline void reserve(size_type n) { _M_vec.reserve(n); }
inline const_reference operator[](size_type n) const { return _M_vec[n]; }
inline const_reference at(size_type n) const { return _M_vec.at(n); }
inline void push_back(const point<_Tp>& p) {
if (_M_vec.empty()) {
_M_vec.push_back(p);
return;
}
_M_vec.push_back(p);
_S_convex(_M_vec);
}
template <typename... _Args>
inline void emplace_back(_Args&&... args) {
_M_vec.emplace_back(args...);
_S_convex(_M_vec);
}
inline double diameter() const { return sqrt((double)_S_diameter(_M_vec)); }
inline _Tp diameter_sqr() const { return _S_diameter(_M_vec); }
inline void merge(const convex_hull<_Tp, _Alloc>& b) {
size_t n = size(), m = b.size();
decltype(_M_vec) A, B;
for (size_t i = 0; i < n; i++) A.push_back(_M_vec[(i + 1) % n] - _M_vec[i]);
for (size_t i = 0; i < m; i++) B.push_back(b[(i + 1) % m] - b[i]);
decltype(_M_vec) res;
size_t i = 0, j = 0, cnt = 0;
res.push_back(_M_vec[0] + b[0]);
while (i < n && j < m) {
res.push_back(res[cnt] + (_S_sign(A[i] * B[j]) >= 0 ? A[i++] : B[j++]));
++cnt;
}
while (i < n) {
res.push_back(res[cnt] + A[i++]);
++cnt;
}
while (j < m) {
res.push_back(res[cnt] + B[j++]);
++cnt;
}
_M_vec = res;
_S_convex(_M_vec);
}
inline bool inside(const point<_Tp>& poi) const {
point<_Tp> t = _M_vec[0];
if (_S_sign((poi - t) * (_M_vec[0] - t)) > 0 || _S_sign((*_M_vec.rbegin() - t) * (poi - t)) > 0) return false;
iterator p = std::lower_bound(_M_vec.begin(), _M_vec.end(), poi, [=](const point<_Tp>& a, const point<_Tp>& b) { return cmp2(a - t, b - t); });
--p;
point<_Tp> i = *p, j;
++p;
if (p == _M_vec.end()) j = _M_vec[0];
else j = *p;
return _S_sign((poi - i) * (j - i)) <= 0;
}
};
```
by Ruiqun2009 @ 2022-12-10 23:02:01