関数
- 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
