#include <iostream> #include <vector> #include <cmath> using namespace std; class Point{ public: double x, y; Point() {} Point(double x, double y): x(x), y(y) {} }; class Vector{ public: double x, y; Vector() {} Vector(Point a, Point b): x(a.x-b.x), y(a.y-b.y) {} }; double cross_product(Vector p, Vector q) { return p.x * q.y - q.x * p.y; } int sign(double x) { if (x > 0) return 1; if (x < 0) return -1; return 0; } bool intersect_line_segm(Point a, Point b, Point c, Point d) { int s1 = sign(cross_product(Vector(a, b), Vector(a, c))); int s2 = sign(cross_product(Vector(a, b), Vector(a, d))); return (s1 == 0 || s2 == 0 || s1 != s2); } bool intersect_1d(double l1, double r1, double l2, double r2) { if (l1 > r1) swap(l1, r1); if (l2 > r2) swap(l2, r2); return r1 >= l2 && r2 >= l1; } bool intersect_segments(Point a, Point b, Point c, Point d) { if (cross_product(Vector(a, b), Vector(a, c)) == 0 && cross_product(Vector(a, b), Vector(a, d)) == 0) { return intersect_1d(a.x, b.x, c.x, d.x) && intersect_1d(a.y, b.y, c.y, d.y); } return intersect_line_segm(a, b, c, d) && intersect_line_segm(c, d, a, b); } double area(vector<Point> A) { double res = 0; for(int i = 1; i < A.size() - 1; i ++) { res += cross_product(Vector(A[0], A[i]), Vector(A[0], A[i + 1])) / 2; } res = abs(res); return res; }