library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub yuruhi/library

:heavy_check_mark: Geometry/Polygon.hpp

Depends on

Required by

Verified with

Code

#pragma once
#include "./Geometric.hpp"
#include "./Vec2.hpp"
#include "./Line.hpp"
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>

namespace Geometric {

	struct Polygon : std::vector<Vec2> {
	public:
		Polygon() = default;
		Polygon(std::size_t n) : std::vector<Vec2>(n) {}
		Polygon(const std::vector<Vec2>& _p) : std::vector<Vec2>(_p) {}
		LD area() const {
			LD ans = 0;
			for (std::size_t i = 0; i < size(); ++i) {
				std::size_t next = i != size() - 1 ? i + 1 : 0;
				ans += at(i).cross(at(next));
			}
			return std::abs(ans) / 2;
		}
		// 凸性判定（反時計回り）
		bool is_convex() const {
			if (size() < 3) {
				return false;
			}
			for (std::size_t i = 0; i < size(); ++i) {
				std::size_t prev = i != 0 ? i - 1 : size() - 1;
				std::size_t next = i != size() - 1 ? i + 1 : 0;
				if (iSP(at(prev), at(i), at(next)) == -1) {
					return false;
				}
			}
			return true;
		}
		// 凸包（反時計回り）
		Polygon convex_hull() const {
			std::vector<Vec2> ps = *this;
			std::sort(ps.begin(), ps.end(), Vec2::compare_xy);
			int n = ps.size(), k = 0;
			Polygon result(2 * n);
			for (int i = 0; i < n; result[k++] = ps[i++]) {
				while (k >= 2 && iSP(result[k - 2], result[k - 1], ps[i]) <= 0) {
					--k;
				}
			}
			for (int i = n - 2, t = k + 1; i >= 0; result[k++] = ps[i--]) {
				while (k >= t && iSP(result[k - 2], result[k - 1], ps[i]) <= 0) {
					--k;
				}
			}
			result.resize(k - 1);
			return result;
		}
		// 凸包（一直線上の3点を含めない、反時計回り）
		Polygon convex_hull_no_collinear() const {
			std::vector<Vec2> ps = *this;
			std::sort(ps.begin(), ps.end(), Vec2::compare_xy);
			int n = ps.size(), k = 0;
			Polygon result(2 * n);
			for (int i = 0; i < n; result[k++] = ps[i++]) {
				while (k >= 2 && iSP(result[k - 2], result[k - 1], ps[i]) != -1) {
					--k;
				}
			}
			for (int i = n - 2, t = k + 1; i >= 0; result[k++] = ps[i--]) {
				while (k >= t && iSP(result[k - 2], result[k - 1], ps[i]) != -1) {
					--k;
				}
			}
			result.resize(k - 1);
			return result;
		}
		// 直径
		std::tuple<LD, std::size_t, std::size_t> diameter() const {
			std::size_t i_start = 0, j_start = 0;
			for (std::size_t i = 1; i < size(); ++i) {
				if (at(i).y > at(i_start).y) i_start = i;
				if (at(i).y < at(j_start).y) j_start = i;
			}
			LD max_dist = (at(i_start) - at(j_start)).length();

			auto diff = [&](int i) {
				return at((i + 1) % size()) - at(i);
			};

			std::size_t i = i_start, i_max = i_start;
			std::size_t j = j_start, j_max = j_start;
			do {
				if (diff(i).cross(diff(j)) >= 0) {
					j = (j + 1) % size();
				} else {
					i = (i + 1) % size();
				}
				if (LD d = (at(i) - at(j)).length(); max_dist < d) {
					max_dist = d;
					i_max = i;
					j_max = j;
				}
			} while (i != i_start || j != j_start);
			return {max_dist, i_max, j_max};
		}
		// 切断
		Polygon cut(const Line& l) const {
			Polygon result;
			for (std::size_t i = 0; i < size(); ++i) {
				Vec2 a = at(i), b = at(i != size() - 1 ? i + 1 : 0);
				if (iSP(l.begin, l.end, a) != -1) {
					result.push_back(a);
				}
				if (iSP(l.begin, l.end, a) * iSP(l.begin, l.end, b) < 0) {
					result.push_back(*cross_point(Line(a, b), l));
				}
			}
			return result;
		}
		friend std::ostream& operator<<(std::ostream& os, const Polygon& p) {
			os << "{";
			for (std::size_t i = 0; i < p.size(); ++i) {
				if (i != 0) os << ", ";
				os << p[i];
			}
			return os << "}";
		}
		friend std::istream& operator>>(std::istream& is, Polygon& p) {
			for (auto& v : p) {
				is >> v;
			}
			return is;
		}
	};

}  // namespace Geometric
#line 2 "Geometry/Geometric.hpp"
#include <iostream>
#include <vector>
#include <algorithm>
#include <optional>

namespace Geometric {

	using LD = long double;
	constexpr long double PI = 3.14159265358979323846, EPS = 1e-12;

	// a > 0 : +1
	// a = 0 :  0
	// a < 0 : -1
	constexpr int sgn(LD a);
	constexpr LD deg_to_rad(LD deg);
	constexpr LD rad_to_deg(LD rad);

	struct Vec2;
	struct Line;
	struct Segment;
	struct Rect;
	struct Circle;
	struct Polygon;

	// AB から見て BC が左に曲がる   : +1
	// AB から見て BC が右に曲がる   : -1
	// ABC, CBA の順に一直線上に並ぶ : +2
	// ACB, BCA の順に一直線上に並ぶ :  0
	// BAC, CAB の順に一直線上に並ぶ : -2
	int iSP(const Vec2& a, const Vec2& b, const Vec2& c);

	// ∠ABC が鋭角 : 0, 直角 : 1, 鈍角 : 2
	int angle_type(const Vec2& a, const Vec2& b, const Vec2& c);

	// ∠ABC の値 (radian)
	LD angle(const Vec2& a, const Vec2& b, const Vec2& c);

	// 距離
	LD distance(const Vec2& v1, const Vec2& v2);
	LD distance(const Vec2& v, const Line& l);
	LD distance(const Vec2& v, const Segment& s);
	LD distance(const Vec2& v, const Circle& c);
	LD distance(const Line& l, const Vec2& v);
	LD distance(const Line& l1, const Line& l2);
	LD distance(const Segment& s, const Vec2& v);
	LD distance(const Segment& s1, const Segment& s2);
	LD distance(const Circle& c, const Vec2& v);
	LD distance(const Circle& c1, const Circle& c2);

	// 交差判定 （内包しているときも true を返す）
	bool intersect(const Vec2& v1, const Vec2& v2);
	bool intersect(const Vec2& v, const Line& l);
	bool intersect(const Vec2& v, const Segment& l);
	bool intersect(const Vec2& v, const Circle& c);
	bool intersect(const Vec2& v, const Rect& r);
	bool intersect(const Vec2& v, const Polygon& p);
	bool intersect(const Line& l, const Vec2& v);
	bool intersect(const Line& l1, const Line& l2);
	bool intersect(const Line& l, const Circle& c);
	bool intersect(const Segment& l, const Vec2& v);
	bool intersect(const Segment& s1, const Segment& s2);
	bool intersect(const Segment& s, const Circle& c);
	bool intersect(const Circle& c, const Vec2& v);
	bool intersect(const Circle& c, const Line& l);
	bool intersect(const Circle& c, const Segment& s);
	bool intersect(const Circle& c1, const Circle& c2);
	bool intersect(const Circle& c, const Rect& r);
	bool intersect(const Rect& r, const Vec2& v);
	bool intersect(const Rect& r1, const Rect& r2);
	bool intersect(const Rect& r, const Circle& c);
	bool intersect(const Polygon& p, const Vec2& v);

	// 接するか判定
	bool tangent(const Vec2& v1, const Vec2& v2);
	bool tangent(const Vec2& v, const Line& l);
	bool tangent(const Vec2& v, const Segment& l);
	bool tangent(const Vec2& v, const Circle& c);
	bool tangent(const Vec2& v, const Rect& r);
	bool tangent(const Vec2& v, const Polygon& p);
	bool tangent(const Line& l, const Vec2& v);
	bool tangent(const Line& l, const Circle& c);
	bool tangent(const Line& l, const Rect& r);
	bool tangent(const Segment& l, const Vec2& v);
	bool tangent(const Circle& c, const Vec2& v);
	bool tangent(const Circle& c, const Line& l);
	bool tangent(const Circle& c1, const Circle& c2);
	bool tangent(const Rect& r, const Vec2& v);
	bool tangent(const Rect& r, const Line& l);
	bool tangent(const Polygon& p, const Vec2& v);

	// 交点
	std::optional<Vec2> cross_point(const Line& l1, const Line& l2);
	std::optional<Vec2> cross_point(const Segment& s1, const Segment& s2);

	std::vector<Vec2> cross_points(const Line& l, const Circle& c);
	std::vector<Vec2> cross_points(const Segment& s, const Circle& c);
	std::vector<Vec2> cross_points(const Circle& c, const Line& l);
	std::vector<Vec2> cross_points(const Circle& c, const Segment& s);
	std::vector<Vec2> cross_points(const Circle& c1, const Circle& c2);

	// 円の接線
	std::vector<Vec2> tangent_to_circle(const Circle& c, const Vec2& v);
}  // namespace Geometric
#line 4 "Geometry/Vec2.hpp"
#include <utility>
#include <cmath>

namespace Geometric {

	struct Vec2 {
		LD x, y;
		static constexpr bool compare_x(const Vec2& v1, const Vec2& v2) {
			return v1.x < v2.x;
		}
		static constexpr bool compare_y(const Vec2& v1, const Vec2& v2) {
			return v1.y < v2.y;
		}
		static constexpr bool compare_xy(const Vec2& v1, const Vec2& v2) {
			return std::make_pair(v1.x, v1.y) < std::make_pair(v2.x, v2.y);
		}
		static constexpr bool compare_yx(const Vec2& v1, const Vec2& v2) {
			return std::make_pair(v1.y, v1.x) < std::make_pair(v2.y, v2.x);
		}
		static constexpr Vec2 zero() {
			return Vec2(0, 0);
		}
		constexpr Vec2() : x(0), y(0) {}
		constexpr Vec2(LD _x, LD _y) : x(_x), y(_y) {}
		Vec2(LD rad) : x(std::cos(rad)), y(std::sin(rad)) {}
		constexpr bool operator==(const Vec2& v) const {
			return sgn(x - v.x) == 0 && sgn(y - v.y) == 0;
		}
		constexpr bool operator!=(const Vec2& v) const {
			return !(*this == v);
		}
		constexpr Vec2 operator+() const {
			return *this;
		}
		constexpr Vec2 operator-() const {
			return {-x, -y};
		}
		constexpr Vec2 operator+(const Vec2& v) const {
			return Vec2(*this) += v;
		}
		constexpr Vec2 operator-(const Vec2& v) const {
			return Vec2(*this) -= v;
		}
		constexpr Vec2 operator*(const Vec2& v) const {
			return Vec2(*this) *= v;
		}
		constexpr Vec2 operator/(const Vec2& v) const {
			return Vec2(*this) /= v;
		}
		constexpr Vec2 operator+(LD n) const {
			return Vec2(*this) += n;
		}
		constexpr Vec2 operator-(LD n) const {
			return Vec2(*this) -= n;
		}
		constexpr Vec2 operator*(LD n) const {
			return Vec2(*this) *= n;
		}
		constexpr Vec2 operator/(LD n) const {
			return Vec2(*this) /= n;
		}
		constexpr Vec2& operator+=(const Vec2& v) {
			x += v.x;
			y += v.y;
			return *this;
		}
		constexpr Vec2& operator-=(const Vec2& v) {
			x -= v.x;
			y -= v.y;
			return *this;
		}
		constexpr Vec2& operator*=(const Vec2& v) {
			x *= v.x;
			y *= v.y;
			return *this;
		}
		constexpr Vec2& operator/=(const Vec2& v) {
			x /= v.x;
			y /= v.y;
			return *this;
		}
		constexpr Vec2& operator+=(LD n) {
			x += n;
			y += n;
			return *this;
		}
		constexpr Vec2& operator-=(LD n) {
			x -= n;
			y -= n;
			return *this;
		}
		constexpr Vec2& operator*=(LD n) {
			x *= n;
			y *= n;
			return *this;
		}
		constexpr Vec2& operator/=(LD n) {
			x /= n;
			y /= n;
			return *this;
		}
		constexpr LD operator[](size_t i) const {
			return i == 0 ? x : i == 1 ? y : 0;
		}
		constexpr std::pair<LD, LD> pair() const {
			return {x, y};
		}
		LD manhattan(const Vec2& v) const {
			return std::abs(x - v.x) + std::abs(y - v.y);
		}
		constexpr LD length_square() const {
			return dot(*this);
		}
		LD length() const {
			return std::sqrt(length_square());
		}
		// 内積
		constexpr LD dot(const Vec2& v) const {
			return x * v.x + y * v.y;
		}
		// 外積
		constexpr LD cross(const Vec2& v) const {
			return x * v.y - y * v.x;
		}
		// 正規化（長さを1にした）ベクトル
		Vec2 normalized() const {
			return *this / length();
		}
		// 原点中心に rad 回転した座標
		Vec2 rotation(LD rad) const {
			LD c = std::cos(rad), s = std::sin(rad);
			return {x * c - y * s, x * s + y * c};
		}
		// 原点中心の円上に乗っているとしたときの偏角
		LD angle() const {
			return std::atan2(y, x);
		}
		// 正射影
		Vec2 projection(const Line& l) const;
		// 鏡映変換
		Vec2 reflection(const Line& l) const;
		constexpr Vec2 rotate90() const {
			return {y, -x};
		}
		constexpr Vec2 rotate180() const {
			return {-x, -y};
		}
		constexpr Vec2 rotate270() const {
			return {-y, x};
		}
		friend std::ostream& operator<<(std::ostream& os, const Vec2& v) {
			return os << '(' << v.x << ", " << v.y << ')';
		}
		friend std::istream& operator>>(std::istream& is, Vec2& v) {
			return is >> v.x >> v.y;
		}
	};

}  // namespace Geometric
#line 6 "Geometry/Line.hpp"
#include <tuple>
#line 8 "Geometry/Line.hpp"

namespace Geometric {

	namespace internal {
		struct LineBase {
		protected:
			constexpr LineBase() = default;
			constexpr LineBase(const Vec2& _begin, const Vec2& _end)
			    : begin(_begin), end(_end) {}
			constexpr LineBase(LD begin_x, LD begin_y, LD end_x, LD end_y)
			    : begin(begin_x, begin_y), end(end_x, end_y) {}

		public:
			Vec2 begin, end;
			constexpr LineBase operator+(const Vec2& v) {
				return LineBase(*this) += v;
			}
			constexpr LineBase operator-(const Vec2& v) {
				return LineBase(*this) -= v;
			}
			constexpr LineBase& operator+=(const Vec2& v) {
				begin += v;
				end += v;
				return *this;
			}
			constexpr LineBase& operator-=(const Vec2& v) {
				begin -= v;
				end -= v;
				return *this;
			}
			constexpr Vec2 vec() const {
				return end - begin;
			}
			constexpr Vec2 counter_vec() const {
				return begin - end;
			}
			// 平行判定
			constexpr bool is_parallel(const LineBase& l) const {
				return sgn(vec().cross(l.vec())) == 0;
			}
			// 直交判定
			constexpr bool is_orthogonal(const LineBase& l) const {
				return sgn(vec().dot(l.vec())) == 0;
			}
			friend std::ostream& operator<<(std::ostream& os, const LineBase& l) {
				return os << '(' << l.begin << ", " << l.end << ')';
			}
			friend std::istream& operator>>(std::istream& is, LineBase& l) {
				return is >> l.begin >> l.end;
			}
		};
	}  // namespace internal

	struct Line : internal::LineBase {
		constexpr Line() = default;
		constexpr Line(const Vec2& _begin, const Vec2& _end) : LineBase(_begin, _end) {}
		constexpr Line(LD begin_x, LD begin_y, LD end_x, LD end_y)
		    : LineBase(begin_x, begin_y, end_x, end_y) {}
		constexpr Line(const LineBase& l) : LineBase(l) {}
		// ax + by + c = 0 の式に変形する
		std::tuple<LD, LD, LD> abc() const {
			if (sgn(begin.x - end.x) == 0) {
				return {1, 0, -begin.x};
			} else {
				LD slope = (end.y - begin.y) / (end.x - begin.x);
				return {slope, -1, begin.y - begin.x * slope};
			}
		}
	};

	struct Segment : internal::LineBase {
		constexpr Segment() = default;
		constexpr Segment(const Vec2& _begin, const Vec2& _end) : LineBase(_begin, _end) {}
		constexpr Segment(LD begin_x, LD begin_y, LD end_x, LD end_y)
		    : LineBase(begin_x, begin_y, end_x, end_y) {}
		constexpr Segment(const LineBase& l) : LineBase(l) {}
	};

}  // namespace Geometric
#line 10 "Geometry/Polygon.hpp"

namespace Geometric {

	struct Polygon : std::vector<Vec2> {
	public:
		Polygon() = default;
		Polygon(std::size_t n) : std::vector<Vec2>(n) {}
		Polygon(const std::vector<Vec2>& _p) : std::vector<Vec2>(_p) {}
		LD area() const {
			LD ans = 0;
			for (std::size_t i = 0; i < size(); ++i) {
				std::size_t next = i != size() - 1 ? i + 1 : 0;
				ans += at(i).cross(at(next));
			}
			return std::abs(ans) / 2;
		}
		// 凸性判定（反時計回り）
		bool is_convex() const {
			if (size() < 3) {
				return false;
			}
			for (std::size_t i = 0; i < size(); ++i) {
				std::size_t prev = i != 0 ? i - 1 : size() - 1;
				std::size_t next = i != size() - 1 ? i + 1 : 0;
				if (iSP(at(prev), at(i), at(next)) == -1) {
					return false;
				}
			}
			return true;
		}
		// 凸包（反時計回り）
		Polygon convex_hull() const {
			std::vector<Vec2> ps = *this;
			std::sort(ps.begin(), ps.end(), Vec2::compare_xy);
			int n = ps.size(), k = 0;
			Polygon result(2 * n);
			for (int i = 0; i < n; result[k++] = ps[i++]) {
				while (k >= 2 && iSP(result[k - 2], result[k - 1], ps[i]) <= 0) {
					--k;
				}
			}
			for (int i = n - 2, t = k + 1; i >= 0; result[k++] = ps[i--]) {
				while (k >= t && iSP(result[k - 2], result[k - 1], ps[i]) <= 0) {
					--k;
				}
			}
			result.resize(k - 1);
			return result;
		}
		// 凸包（一直線上の3点を含めない、反時計回り）
		Polygon convex_hull_no_collinear() const {
			std::vector<Vec2> ps = *this;
			std::sort(ps.begin(), ps.end(), Vec2::compare_xy);
			int n = ps.size(), k = 0;
			Polygon result(2 * n);
			for (int i = 0; i < n; result[k++] = ps[i++]) {
				while (k >= 2 && iSP(result[k - 2], result[k - 1], ps[i]) != -1) {
					--k;
				}
			}
			for (int i = n - 2, t = k + 1; i >= 0; result[k++] = ps[i--]) {
				while (k >= t && iSP(result[k - 2], result[k - 1], ps[i]) != -1) {
					--k;
				}
			}
			result.resize(k - 1);
			return result;
		}
		// 直径
		std::tuple<LD, std::size_t, std::size_t> diameter() const {
			std::size_t i_start = 0, j_start = 0;
			for (std::size_t i = 1; i < size(); ++i) {
				if (at(i).y > at(i_start).y) i_start = i;
				if (at(i).y < at(j_start).y) j_start = i;
			}
			LD max_dist = (at(i_start) - at(j_start)).length();

			auto diff = [&](int i) {
				return at((i + 1) % size()) - at(i);
			};

			std::size_t i = i_start, i_max = i_start;
			std::size_t j = j_start, j_max = j_start;
			do {
				if (diff(i).cross(diff(j)) >= 0) {
					j = (j + 1) % size();
				} else {
					i = (i + 1) % size();
				}
				if (LD d = (at(i) - at(j)).length(); max_dist < d) {
					max_dist = d;
					i_max = i;
					j_max = j;
				}
			} while (i != i_start || j != j_start);
			return {max_dist, i_max, j_max};
		}
		// 切断
		Polygon cut(const Line& l) const {
			Polygon result;
			for (std::size_t i = 0; i < size(); ++i) {
				Vec2 a = at(i), b = at(i != size() - 1 ? i + 1 : 0);
				if (iSP(l.begin, l.end, a) != -1) {
					result.push_back(a);
				}
				if (iSP(l.begin, l.end, a) * iSP(l.begin, l.end, b) < 0) {
					result.push_back(*cross_point(Line(a, b), l));
				}
			}
			return result;
		}
		friend std::ostream& operator<<(std::ostream& os, const Polygon& p) {
			os << "{";
			for (std::size_t i = 0; i < p.size(); ++i) {
				if (i != 0) os << ", ";
				os << p[i];
			}
			return os << "}";
		}
		friend std::istream& operator>>(std::istream& is, Polygon& p) {
			for (auto& v : p) {
				is >> v;
			}
			return is;
		}
	};

}  // namespace Geometric
Back to top page