Felix's Library
This documentation is automatically generated by online-judge-tools/verification-helper
library/geometry/point-in-convex-hull.hpp
- View this file on GitHub
- Last update: 2023-05-26 16:40:39+08:00
- Include:
#include "library/geometry/point-in-convex-hull.hpp"
Depends on
library/geometry/geometry.hpp
Code
#pragma once
#include <vector>
#include "point.hpp"
#include "geometry.hpp"
namespace felix {
namespace geometry {
// Convex Hull must be sorted in counter-clockwise order
// ON: -1, IN: +1, OUT: 0
template<class T>
int point_in_convex_hull(const std::vector<Point<T>>& a, const Point<T>& p) {
int n = (int) a.size();
if(between(a[0], a[1], p) || between(a[0], a[n - 1], p)) {
return -1;
}
int l = 0, r = n - 1;
while(l <= r) {
int m = (l + r) / 2;
auto a1 = cross(a[m] - a[0], p - a[0]);
auto a2 = cross(a[(m + 1) % n] - a[0], p - a[0]);
if(a1 >= 0 && a2 <= 0) {
auto res = cross(a[(m + 1) % n] - a[m], p - a[m]);
return res > 0 ? 1 : (res >= 0 ? -1 : 0);
}
if(a1 < 0) {
r = m - 1;
} else {
l = m + 1;
}
}
return 0;
}
} // namespace geometry
} // namespace felix#line 2 "library/geometry/point-in-convex-hull.hpp"
#include <vector>
#line 2 "library/geometry/point.hpp"
#include <iostream>
#include <cmath>
namespace felix {
namespace geometry {
template<class T>
struct Point {
T x, y;
Point(T a = 0, T b = 0) : x(a), y(b) {}
Point(const std::pair<T, T>& p) : x(p.first), y(p.second) {}
explicit constexpr operator std::pair<T, T>() const { return std::pair<T, T>(x, y); }
constexpr Point& operator+=(const Point& rhs) & {
x += rhs.x, y += rhs.y;
return *this;
}
constexpr Point& operator-=(const Point& rhs) & {
x -= rhs.x, y -= rhs.y;
return *this;
}
constexpr Point& operator*=(const T& rhs) & {
x *= rhs, y *= rhs;
return *this;
}
constexpr Point& operator/=(const T& rhs) & {
x /= rhs, y /= rhs;
return *this;
}
constexpr Point operator+() const { return *this; }
constexpr Point operator-() const { return Point(-x, -y); }
friend constexpr Point operator+(Point lhs, Point rhs) { return lhs += rhs; }
friend constexpr Point operator-(Point lhs, Point rhs) { return lhs -= rhs; }
friend constexpr Point operator*(Point lhs, T rhs) { return lhs *= rhs; }
friend constexpr Point operator/(Point lhs, T rhs) { return lhs /= rhs; }
constexpr bool operator==(const Point& rhs) const { return x == rhs.x && y == rhs.y; }
constexpr bool operator!=(const Point& rhs) const { return !(*this == rhs); }
// rotate counter-clockwise
constexpr Point rotate(T theta) const {
T sin_t = std::sin(theta), cos_t = std::cos(theta);
return Point(x * cos_t - y * sin_t, x * sin_t + y * cos_t);
}
friend constexpr T abs2(Point p) { return p.x * p.x + p.y * p.y; }
friend constexpr long double abs(Point p) { return std::sqrt(abs2(p)); }
friend constexpr long double angle(Point p) { return std::atan2(p.y, p.x); }
friend constexpr T dot(Point lhs, Point rhs) { return lhs.x * rhs.x + lhs.y * rhs.y; }
friend constexpr T cross(Point lhs, Point rhs) { return lhs.x * rhs.y - lhs.y * rhs.x; }
friend constexpr std::istream& operator>>(std::istream& in, Point& p) {
return in >> p.x >> p.y;
}
};
} // namespace geometry
} // namespace felix
#line 3 "library/geometry/geometry.hpp"
#include <algorithm>
#line 4 "library/geometry/line.hpp"
namespace felix {
namespace geometry {
template<class T>
struct Line {
Point<T> a, b;
Line() {}
Line(Point<T> _a, Point<T> _b) : a(_a), b(_b) {}
constexpr Point<T> vectorize() const { return b - a; }
friend constexpr std::istream& operator>>(std::istream& in, Line& l) {
return in >> l.a >> l.b;
}
};
} // namespace geometry
} // namespace felix
#line 6 "library/geometry/geometry.hpp"
namespace felix {
namespace geometry {
namespace internal {
template<class T> constexpr int sign(T x) { return x == 0 ? 0 : (x < 0 ? -1 : +1); }
} // namespace internal
// LEFT: +1, RIGHT: -1, STRAIGHT: 0
template<class T>
int orientation(Point<T> a, Point<T> b, Point<T> c) {
return internal::sign(cross(b - a, c - a));
}
template<class T>
bool collinearity(Point<T> a, Point<T> b, Point<T> c) {
return internal::sign(cross(a - c, b - c)) == 0;
}
template<class T>
bool between(Point<T> a, Point<T> b, Point<T> c) {
return collinearity(a, c, b) && internal::sign(dot(a - b, c - b)) <= 0;
}
template<class T>
bool segment_intersection(Line<T> a, Line<T> b) {
int a123 = orientation(a.a, a.b, b.a);
int a124 = orientation(a.a, a.b, b.b);
int a341 = orientation(b.a, b.b, a.a);
int a342 = orientation(b.a, b.b, a.b);
if(a123 == 0 && a124 == 0) {
return between(a.a, b.a, a.b) || between(a.a, b.b, a.b) || between(b.a, a.a, b.b) || between(b.a, a.b, b.b);
}
return a123 * a124 <= 0 && a341 * a342 <= 0;
}
template<class T>
Point<T> line_intersection(Line<T> a, Line<T> b) {
T a123 = cross(a.vectorize(), b.a - a.a);
T a124 = cross(a.vectorize(), b.b - a.a);
return (b.b * a123 - b.a * a124) / (a123 - a124);
}
template<class T>
Point<T> projection(Line<T> L, Point<T> p) {
auto v = L.vectorize();
T x = abs(v);
return L.a + v / x * dot(p - L.a, v) / x;
}
template<class T>
Point<T> reflection(Line<T> L, Point<T> p) {
auto proj = projection(L, p);
return p + (proj - p) * 2;
}
} // namespace geometry
} // namespace felix
#line 5 "library/geometry/point-in-convex-hull.hpp"
namespace felix {
namespace geometry {
// Convex Hull must be sorted in counter-clockwise order
// ON: -1, IN: +1, OUT: 0
template<class T>
int point_in_convex_hull(const std::vector<Point<T>>& a, const Point<T>& p) {
int n = (int) a.size();
if(between(a[0], a[1], p) || between(a[0], a[n - 1], p)) {
return -1;
}
int l = 0, r = n - 1;
while(l <= r) {
int m = (l + r) / 2;
auto a1 = cross(a[m] - a[0], p - a[0]);
auto a2 = cross(a[(m + 1) % n] - a[0], p - a[0]);
if(a1 >= 0 && a2 <= 0) {
auto res = cross(a[(m + 1) % n] - a[m], p - a[m]);
return res > 0 ? 1 : (res >= 0 ? -1 : 0);
}
if(a1 < 0) {
r = m - 1;
} else {
l = m + 1;
}
}
return 0;
}
} // namespace geometry
} // namespace felix