7K12 blog

猫でも分かるアルゴリズム解説

幾何ライブラリ

  • Point: 座標
  • Line: 直線
  • Circle: 円
  • Vector: ベクトル(=Point)
  • Polygon: 多角形(ベクトルの配列)

関数

  • bool intersect(Line l1, Line l2): 直線L1と直線L2の交差判定
#include <bits/stdc++.h>
using namespace std;

namespace LIB
{
	const long double eps = 1e-10;
	using ld = long double;	
	struct Point;
	struct Line;
	struct Circle;
	using Vector = Point;
	using Polygon = vector<Point>;
	enum ccw_type {  clock_wise = -1, on_segment, counter_clock_wise, online_back, online_front, };
	ccw_type ccw_check(Point& p1, Point& p2, Point& p3);
	ld cross(Vector a, Vector b);
	ld distance(Point& p1, Point& p2);
	ld distance(Point& p, Line& l);
	ld dot(Vector a, Vector b);
	template <class T> bool equals(T a, T b);
	bool intersect(Line l1, Line l2);
	bool intersect(Point p1, Point p2, Point p3, Point p4);
	bool orthogonal(Vector& v1, Vector& v2);
	bool orthogonal(Line& l1, Line& l2);
	bool parallel(Vector& v1, Vector& v2);
	bool parallel(Line& l1, Line& l2);

	struct Point {
		ld x, y;
		Point():x(0),y(0){}
		Point(pair<ld,ld> xy):x(xy.first),y(xy.second){}
		Point operator + (Point p) { return Point({x+p.x,y+p.y}); }
		Point operator - (Point p) { return Point({x-p.x,y-p.y}); }
		Point operator * (Point p) { return Point({x*p.x,y*p.y}); }
		Point operator / (Point p) { return Point({x/p.x,y/p.y}); }
		bool operator == (const Point &p) const { return equals(x,p.x) && equals(y,p.y); }
		bool operator != (const Point &p) const { return !(equals(x,p.x) && equals(y,p.y)); }
		ld abs() { return sqrtl(norm()); }
		bool equals(ld a, ld b) const { return fabsl(a-b)<eps; }
		void load(pair<ld,ld> p) { x=p.first,y=p.second; }
		ld norm() { return x*x+y*y; }
	};

	struct Line {
		Point p1,p2;
		Line(){}
		Line(Point _p1, Point _p2) : p1(_p1), p2(_p2) {};
		Line(pair<ld,ld> _p1, pair<ld,ld> _p2) : p1(_p1), p2(_p2) {};
		void load(Point _p1, Point _p2) { p1=_p1,p2=_p2; }
		void load(pair<ld,ld> _p1, pair<ld,ld> _p2) { p1.load(_p1),p2.load(_p2); }
	};

	struct Circle {
		ld r;
		Point c;
		Circle(Point c, ld r) : r(r), c(c) {}
	};

	ld cross(Vector a, Vector b) { return a.x*b.y-a.y*b.x; }
	ld distance(Point& p1, Point& p2) { return (p1-p2).abs(); }
	ld distance(Point& p, Line& l) { return  abs(cross(l.p2-l.p1,p-l.p1)/(l.p2-l.p1).abs()); }
	ld dot(Vector a, Vector b) { return a.x*b.x+a.y*b.y; }
	template <class T> bool equals(T a, T b) { return fabsl(a-b)<eps; }
	bool intersect(Line l1, Line l2){ return intersect(l1.p1,l1.p2,l2.p1,l2.p2); }
	bool intersect(Point p1, Point p2, Point p3, Point p4){ return (ccw_check(p1,p2,p3)*ccw_check(p1,p2,p4)<=0&&ccw_check(p3,p4,p1)*ccw_check(p3,p4,p2)<=0); }
	bool orthogonal(Vector& v1, Vector& v2) { return equals(dot(v1,v2),0.0l); }
	bool orthogonal(Line& l1, Line& l2) { return equals(dot(l1.p2-l1.p1,l2.p2-l2.p1),0.0l); }
	bool parallel(Vector& v1, Vector& v2) { return equals(cross(v1, v2),0.0l); }
	bool parallel(Line& l1, Line& l2) { return equals(cross(l1.p2-l1.p1,l2.p2-l2.p1),0.0l); }

	ccw_type ccw_check(Point& p1, Point& p2, Point& p3) {
		Vector v1=p2-p1;
		Vector v2=p3-p1;
		if (cross(v1,v2)>eps) return counter_clock_wise; 
		if (cross(v1,v2)<-eps) return clock_wise;
		if (dot(v1,v2)<-eps) return online_back;
		if (v1.norm()>v2.norm()) return online_front;
		return on_segment;
	}
}

実装例
https://atcoder.jp/contests/abc016/submissions/38359641