12tqian's Competitive Programming Library
This documentation is automatically generated by online-judge-tools/verification-helper
library/geometry/point.hpp
- View this file on GitHub
- Last update: 2022-07-21 16:12:33-04:00
- Include:
#include "library/geometry/point.hpp"
Required by
Verified with
- verify/kattis/kattis-convexhull.test.cpp
- verify/kattis/kattis-pointinpolygon.test.cpp
- verify/yosupo/yosupo-sort_points_by_argument.test.cpp
Code
#pragma once
template <typename T> struct Point {
public:
T x, y;
Point() : x(0), y(0) {}
Point(T x_, T y_) : x(x_), y(y_) {}
template <typename U> explicit Point(const Point<U>& p) : x(p.x), y(p.y) {}
Point(const std::pair<T, T>& p) : x(p.first), y(p.second) {}
Point(const std::complex<T>& p) : x(real(p)), y(imag(p)) {}
explicit operator std::pair<T, T>() const { return std::pair<T, T>(x, y); }
explicit operator std::complex<T>() const { return std::complex<T>(x, y); }
friend std::ostream& operator<<(std::ostream &o, const Point& p) {
return o << '(' << p.x << ',' << p.y << ')'; }
friend std::istream& operator>>(std::istream &i, Point& p) { return i >> p.x >> p.y; }
friend bool operator==(const Point& a, const Point& b) { return a.x == b.x && a.y == b.y; }
friend bool operator!=(const Point& a, const Point& b) { return !(a == b); }
friend bool operator<(const Point& a, const Point& b) {
return (a.x != b.x ? a.x < b.x : a.y < b.y); }
friend T norm(const Point& a) { return a.x * a.x + a.y * a.y; }
friend T abs(const Point& p) { return std::hypot(p.x, p.y); }
friend T unit(const Point& a) { if (a == Point()) return a; return a / abs(a); }
friend Point conj(const Point& a) { return Point(a.x, -a.y); }
friend Point perp(const Point& a) { return Point(-a.y, a.x); }
friend long double arg(const Point& p) { return atan2(p.y, p.x); }
friend Point dir(long double angle) { return Point(cos(angle), sin(angle)); }
Point& operator+=(const Point& p) { x += p.x, y += p.y; return *this; }
Point& operator-=(const Point& p) { x -= p.x, y -= p.y; return *this; }
Point& operator*=(const T &t) { x *= t, y *= t; return *this; }
Point& operator/=(const T &t) { x /= t, y /= t; return *this; }
Point& operator*=(const Point& t) {
Point res = Point(x, y) * t; x = res.x, y = res.y; return *this; }
Point& operator/=(const Point& t) {
Point res = Point(x, y) / t; x = res.x, y = res.y; return *this; }
friend Point operator+(const Point& a, const Point& b) { return Point(a.x + b.x, a.y + b.y); }
friend Point operator-(const Point& a, const Point& b) { return Point(a.x - b.x, a.y - b.y); }
friend Point operator*(const Point& a, const T &t) { return Point(a.x * t, a.y * t); }
friend Point operator*(const T &t ,const Point& a) { return Point(t * a.x, t * a.y); }
friend Point operator/(const Point& a, const T &t) { return Point(a.x / t, a.y / t); }
friend Point operator*(const Point& a, const Point& b) {
return Point(a.x * b.x - a.y * b.y, a.y * b.x + a.x * b.y); }
friend Point operator/(const Point& a, const Point& b) {
return Point(a * conj(b) / norm(b)); }
friend T int_norm(const Point& a) { return __gcd(a.x, a.y); }
friend T int_unit(const Point& a) { if (a == Point()) return a; return a / int_norm(a); }
friend T cross(const Point& a, const Point& b) { return a.x * b.y - a.y * b.x; }
friend T dot(const Point& a, const Point& b) { return a.x * b.x + a.y * b.y; }
friend T area(const Point& a, const Point& b, const Point& c) { return cross(b - a, c - a); }
// Returns conj(a) * b
friend Point rotation(const Point& a, const Point& b) { return Point(dot(a, b), cross(a, b)); }
friend bool same_dir(const Point& a, const Point& b) { return cross(a, b) == 0 && dot(a, b) > 0; }
// check if 180 <= s..t < 360
friend bool is_reflex(const Point& a, const Point& b) {
auto c = cross(a, b); return c ? (c < 0) : (dot(a, b) < 0); }
// operator < (s, t) for angles in [base, base+2pi)
friend bool angle_less(const Point& base, const Point& s, const Point& t) {
int r = is_reflex(base, s) - is_reflex(base, t);
return r ? (r < 0) : (0 < cross(s, t));
}
friend bool angle_cmp(const Point& base) {
return [base](const Point& s, const Point& t) { return angle_less(base, s, t); };
}
friend bool angle_cmp_center(const Point& center, const Point& dir) {
return [center, dir](const Point& s, const Point& t) -> bool {
return angle_less(dir, s - center, t - center); };
}
// is p in [s,t] taken ccw? 1/0/-1 for in/border/out
friend int angle_between(const Point& s, const Point& t, const Point& p) {
if (same_dir(p, s) || same_dir(p, t)) return 0;
return angle_less(s, p, t) ? 1 : -1;
}
};template <typename T> struct Point {
public:
T x, y;
Point() : x(0), y(0) {}
Point(T x_, T y_) : x(x_), y(y_) {}
template <typename U> explicit Point(const Point<U>& p) : x(p.x), y(p.y) {}
Point(const std::pair<T, T>& p) : x(p.first), y(p.second) {}
Point(const std::complex<T>& p) : x(real(p)), y(imag(p)) {}
explicit operator std::pair<T, T>() const { return std::pair<T, T>(x, y); }
explicit operator std::complex<T>() const { return std::complex<T>(x, y); }
friend std::ostream& operator<<(std::ostream &o, const Point& p) {
return o << '(' << p.x << ',' << p.y << ')'; }
friend std::istream& operator>>(std::istream &i, Point& p) { return i >> p.x >> p.y; }
friend bool operator==(const Point& a, const Point& b) { return a.x == b.x && a.y == b.y; }
friend bool operator!=(const Point& a, const Point& b) { return !(a == b); }
friend bool operator<(const Point& a, const Point& b) {
return (a.x != b.x ? a.x < b.x : a.y < b.y); }
friend T norm(const Point& a) { return a.x * a.x + a.y * a.y; }
friend T abs(const Point& p) { return std::hypot(p.x, p.y); }
friend T unit(const Point& a) { if (a == Point()) return a; return a / abs(a); }
friend Point conj(const Point& a) { return Point(a.x, -a.y); }
friend Point perp(const Point& a) { return Point(-a.y, a.x); }
friend long double arg(const Point& p) { return atan2(p.y, p.x); }
friend Point dir(long double angle) { return Point(cos(angle), sin(angle)); }
Point& operator+=(const Point& p) { x += p.x, y += p.y; return *this; }
Point& operator-=(const Point& p) { x -= p.x, y -= p.y; return *this; }
Point& operator*=(const T &t) { x *= t, y *= t; return *this; }
Point& operator/=(const T &t) { x /= t, y /= t; return *this; }
Point& operator*=(const Point& t) {
Point res = Point(x, y) * t; x = res.x, y = res.y; return *this; }
Point& operator/=(const Point& t) {
Point res = Point(x, y) / t; x = res.x, y = res.y; return *this; }
friend Point operator+(const Point& a, const Point& b) { return Point(a.x + b.x, a.y + b.y); }
friend Point operator-(const Point& a, const Point& b) { return Point(a.x - b.x, a.y - b.y); }
friend Point operator*(const Point& a, const T &t) { return Point(a.x * t, a.y * t); }
friend Point operator*(const T &t ,const Point& a) { return Point(t * a.x, t * a.y); }
friend Point operator/(const Point& a, const T &t) { return Point(a.x / t, a.y / t); }
friend Point operator*(const Point& a, const Point& b) {
return Point(a.x * b.x - a.y * b.y, a.y * b.x + a.x * b.y); }
friend Point operator/(const Point& a, const Point& b) {
return Point(a * conj(b) / norm(b)); }
friend T int_norm(const Point& a) { return __gcd(a.x, a.y); }
friend T int_unit(const Point& a) { if (a == Point()) return a; return a / int_norm(a); }
friend T cross(const Point& a, const Point& b) { return a.x * b.y - a.y * b.x; }
friend T dot(const Point& a, const Point& b) { return a.x * b.x + a.y * b.y; }
friend T area(const Point& a, const Point& b, const Point& c) { return cross(b - a, c - a); }
// Returns conj(a) * b
friend Point rotation(const Point& a, const Point& b) { return Point(dot(a, b), cross(a, b)); }
friend bool same_dir(const Point& a, const Point& b) { return cross(a, b) == 0 && dot(a, b) > 0; }
// check if 180 <= s..t < 360
friend bool is_reflex(const Point& a, const Point& b) {
auto c = cross(a, b); return c ? (c < 0) : (dot(a, b) < 0); }
// operator < (s, t) for angles in [base, base+2pi)
friend bool angle_less(const Point& base, const Point& s, const Point& t) {
int r = is_reflex(base, s) - is_reflex(base, t);
return r ? (r < 0) : (0 < cross(s, t));
}
friend bool angle_cmp(const Point& base) {
return [base](const Point& s, const Point& t) { return angle_less(base, s, t); };
}
friend bool angle_cmp_center(const Point& center, const Point& dir) {
return [center, dir](const Point& s, const Point& t) -> bool {
return angle_less(dir, s - center, t - center); };
}
// is p in [s,t] taken ccw? 1/0/-1 for in/border/out
friend int angle_between(const Point& s, const Point& t, const Point& p) {
if (same_dir(p, s) || same_dir(p, t)) return 0;
return angle_less(s, p, t) ? 1 : -1;
}
};