#include using namespace std; const double EPS = 1e-9; void readInt(int &x, int l, int r) { scanf("%d", &x); assert(l <= x && x <= r); } double det(double a, double b, double c, double d) { return a * d - b * c; } bool is_zero(double value) { return fabs(value) < EPS; } bool are_equal(double a, double b) { return is_zero(a - b); } int sgn(double value) { if (is_zero(value)) { return 0; } else if (value < 0.0) { return -1; } else { return 1; } } // c in (a, b) bool is_inner(double a, double b, double c) { if (a > b) { swap(a, b); } return a + EPS < c && c + EPS < b; } struct Point { double x; double y; Point(double x = 0.0, double y = 0.0) : x(x), y(y) {}; }; istream &operator>>(istream &is, Point &p) { is >> p.x >> p.y; return is; } ostream &operator<<(ostream &os, const Point &p) { os << "(" << p.x << ", " << p.y << ")"; return os; } Point operator+(const Point &a, const Point &b) { return Point(a.x + b.x, a.y + b.y); } Point operator-(const Point &a) { return Point(-a.x, -a.y); } Point operator-(const Point &a, const Point &b) { return a + (-b); } double operator*(const Point &a, const Point &b) { return a.x * b.y - a.y * b.x; } double operator%(const Point &a, const Point &b) { return a.x * b.x + a.y * b.y; } bool are_equal(const Point &a, const Point &b) { return are_equal(a.x, b.x) && are_equal(a.y, b.y); } double distance_between(const Point &a, const Point &b) { double dx = a.x - b.x; double dy = a.y - b.y; return sqrt(dx * dx + dy * dy); } struct Line { double a; double b; double c; Line(double a = 0.0, double b = 0.0, double c = 0.0) : a(a), b(b), c(c) {}; Line(const Point &p, const Point &q) { a = p.y - q.y; b = q.x - p.x; c = -a * p.x - b * p.y; } }; double point_offset(const Point &p, const Line &l) { return l.a * p.x + l.b * p.y + l.c; } double distance_between(const Point &p, const Line &l) { return fabs(point_offset(p, l)) / sqrt(l.a * l.a + l.b * l.b); } bool lies_on_a_line(const Point &p, const Line &l) { return is_zero(point_offset(p, l)); } // c in (a, b) bool is_inner(const Point &a, const Point &b, const Point &c) { Line line(a, b); if (!lies_on_a_line(c, line)) { return false; } if (are_equal(a.x, b.x)) { return is_inner(a.y, b.y, c.y); } else { return is_inner(a.x, b.x, c.x); } } // c in [a, b] bool is_inside(const Point &a, const Point &b, const Point &c) { return is_inner(a, b, c) || are_equal(a, b) || are_equal(b, c); } bool intersect_lines(const Line &p, const Line &q, Point &a) { double o = det(p.a, p.b, q.a, q.b); double o_1 = det(-p.c, p.b, -q.c, q.b); double o_2 = det(p.a, -p.c, q.a, -q.c); if (is_zero(o)) { return false; } else { a.x = o_1 / o; a.y = o_2 / o; return true; } } bool have_an_inner_intersection_point(const Point &a, const Point &b, const Point &c, const Point &d) { Line p(a, b); Line q(c, d); Point e; if (intersect_lines(p, q, e)) { return (is_inner(a, b, e) && is_inside(c, d, e)) || (is_inner(c, d, e) && is_inside(a, b, e)); } else { return is_inner(a, b, c) || is_inner(a, b, d) || is_inner(c, d, a) || is_inner(c, d, b); } } bool is_degenerate(int n, Point polygon[]) { if (n < 3) { return true; } for (int i = 0; i < n; i++) { int a = i; int b = (i + 1) % n; if (are_equal(polygon[a], polygon[b])) { return true; } } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int a = i; int b = (i + 1) % n; int c = j; int d = (j + 1) % n; if (have_an_inner_intersection_point(polygon[a], polygon[b], polygon[c], polygon[d])) { return true; } } } return false; } Point triangles[2][3]; Point quadrangle[4]; bool iterate_through_pairs_of_sides(Point triangles[][3], function&, const vector&)> criterion) { vector sides_1 = { distance_between(triangles[0][0], triangles[0][1]), distance_between(triangles[0][1], triangles[0][2]), distance_between(triangles[0][2], triangles[0][0])}; sort(sides_1.begin(), sides_1.end()); do { vector sides_2 = { distance_between(triangles[1][0], triangles[1][1]), distance_between(triangles[1][1], triangles[1][2]), distance_between(triangles[1][2], triangles[1][0])}; sort(sides_2.begin(), sides_2.end()); do { if (criterion(sides_1, sides_2)) { return true; } } while (next_permutation(sides_2.begin(), sides_2.end())); } while (next_permutation(sides_1.begin(), sides_1.end())); return false; } void process_quadrangle_one_way(Point triangles[][3], Point quadrangle[], string &answer) { for (int i = 0; i < 4; i++) { Point a = quadrangle[i]; Point b = quadrangle[(i + 1) % 4]; Point c = quadrangle[(i + 2) % 4]; Point d = quadrangle[(i + 3) % 4]; // first case - one side of the first triangle is put against the same-length side of the second triangle if (sgn((b - a) * (c - a)) * sgn((c - a) * (d - a)) > 0) { vector distances = { distance_between(a, b), distance_between(a, c), distance_between(a, d), distance_between(b, c), distance_between(c, d)}; auto criterion = [distances](const vector &sides_1, const vector &sides_2) { return are_equal(distances[0], sides_1[0]) && are_equal(distances[1], sides_1[1]) && are_equal(distances[1], sides_2[0]) && are_equal(distances[2], sides_2[1]) && are_equal(distances[3], sides_1[2]) && are_equal(distances[4], sides_2[2]); }; if (iterate_through_pairs_of_sides(triangles, criterion)) { answer = "Yes"; } } // second case - one side of the first triangle is put against a longer side of the second triangle if (sgn((c - a) * (b - a)) * sgn((b - a) * (d - a)) > 0) { Point e; intersect_lines(Line(a, b), Line(c, d), e); vector distances = { distance_between(a, d), distance_between(a, e), distance_between(e, d), distance_between(b, e), distance_between(e, c), distance_between(c, b)}; auto criterion = [distances](const vector &sides_1, const vector &sides_2) { return are_equal(distances[0], sides_1[0]) && are_equal(distances[1], sides_1[1]) && are_equal(distances[2], sides_1[2]) && are_equal(distances[3], sides_2[0]) && are_equal(distances[4], sides_2[1]) && are_equal(distances[5], sides_2[2]); }; if (iterate_through_pairs_of_sides(triangles, criterion)) { answer = "Yes"; } } // third case - quadrangle turned out to be a triangle if (lies_on_a_line(c, Line(b, d))) { vector distances = { distance_between(a, b), distance_between(a, d), distance_between(b, d)}; auto criterion = [distances](const vector &sides_1, const vector &sides_2) { return are_equal(distances[0], sides_1[0]) && are_equal(sides_1[1], sides_2[0]) && are_equal(distances[1], sides_2[1]) && are_equal(distances[2], sides_1[2] + sides_2[2]); }; if (iterate_through_pairs_of_sides(triangles, criterion)) { answer = "Yes"; } } } } string process_quadrangle(Point triangles[][3], Point quadrangle[]) { string answer = "No"; process_quadrangle_one_way(triangles, quadrangle, answer); reverse(quadrangle, quadrangle + 4); process_quadrangle_one_way(triangles, quadrangle, answer); return answer; } void solve() { for (int i = 0; i < 2; i++) { for (int j = 0; j < 3; j++) { int x, y; readInt(x, -20000, 20000); readInt(y, -20000, 20000); triangles[i][j] = Point(x, y); } } for (int i = 0; i < 4; i++) { int x, y; readInt(x, -20000, 20000); readInt(y, -20000, 20000); quadrangle[i] = Point(x, y); } assert(!is_degenerate(3, triangles[0])); assert(!is_degenerate(3, triangles[1])); assert(!is_degenerate(4, quadrangle)); string answer = process_quadrangle(triangles, quadrangle); cout << answer << "\n"; } int main() { int cases; readInt(cases, 1, 600); for (int i = 0; i < cases; i++) { solve(); } return 0; }