GeometryTemplate

const ld PI = atan2l(0., -1.);

struct Point { ld x; ld y; };
struct Vector {
  ld x; ld y;
  ld Len() const { return sqrtl(x * x + y * y); }
  ld Len2() const { return x * x + y * y; }
};
struct Line {
  ld a; ld b; ld c;
  Line(const Point& p1, const Point& p2) { a = p1.y - p2.y; b = p2.x - p1.x; c = -a * p1.x - b * p1.y; }
  Line(const Point& p, const Vector& v) { a = v.y; b = -v.x; c = -a * p.x - b * p.y; }
};

bool operator==(const Point& p1, const Point& p2) { return p1.x == p2.x && p1.y == p2.y; }
Point operator-(const Point& p) { return {-p.x, -p.y}; }
Point operator+(const Point& p, const Vector& v) { return {p.x + v.x, p.y + v.y}; }
Point operator+(const Vector& v, const Point& p) { return {p.x + v.x, p.y + v.y}; }
Point operator-(const Point& p, const Vector& v) { return {p.x - v.x, p.y - v.y}; }
Vector operator-(const Point& p1, const Point& p2) { return {p1.x - p2.x, p1.y - p2.y}; }
Vector operator+(const Vector& v1, const Vector& v2) { return {v1.x + v2.x, v1.y + v2.y};}
Vector operator-(const Vector& v1, const Vector& v2) { return {v1.x - v2.x, v1.y - v2.y}; }
ld DotProduct(const Vector& v1, const Vector& v2) { return v1.x * v2.x + v1.y * v2.y; }
ld CrossProduct(const Vector& v1, const Vector& v2) { return v1.x * v2.y - v1.y * v2.x; }
istream& operator>>(istream& in, Point& v) { return in >> v.x >> v.y; }
istream& operator>>(istream& in, Vector& v) { return in >> v.x >> v.y; }
ostream& operator<<(ostream& out, const Point& v) { return out << v.x << " " << v.y; }
ostream& operator<<(ostream& out, const Vector& v) { return out << v.x << " " << v.y; }
bool operator<(const Point& p1, const Point& p2) { return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y); }
namespace std {
  template <> struct hash<Point> {
    size_t operator()(const Point& p) const { return hash<ll>()(p.x) ^ hash<ll>()(p.y); }
  };
}
Point Center(const Point& p1, const Point& p2) { return {(p1.x + p2.x) / 2., (p1.y + p2.y) / 2.}; }
Point Intersection(const Line& l1, const Line& l2) {
  ld d = l1.a * l2.b - l1.b * l2.a;
  if (fabsl(d) < eps) return {INFINITY, INFINITY};
  return {(l2.c * l1.b - l1.c * l2.b) / d, (l1.c * l2.a - l2.c * l1.a) / d};
}