#P2494. Triangles and Quadrangle

    ID: 1549 传统题 1000ms 128MiB 尝试: 5 已通过: 4 难度: 8 上传者: 标签>CF2500提高+/省选-有限候选集缩减暴力枚举点积叉积有理数精确运算平方距离比较鞋带公式高精度乘法多边形半平面裁剪Acm2011上海

Triangles and Quadrangle

题目描述

Little Yuan is two years old and she is learning about some triangles and quadrangles.She is such a smart girl that she soon realizes two triangles can form a quadrangle without overlapping each other.She picks up a lot of triangles and uses them to form some quadrangles.Unfortunately,she is not good at this kind of jigsaw game and makes some mistakes.
As her brother,you are curious about whether she has made a mistake when forming two triangles into a quadrangle.You are thinking about to write a program to determine it.
Notice that the quadrangle in this problem is defined as a simple polygon with four vertexes.And you may also assume that all triangles and quadrangle have positive area.
Note that two graphs are considered as the same if and only if they can overlap completely by shifting,rotation and flipping.You can also shifting,rotation and flipping one of the triangles to form the triangles to a quadrangle.  

输入格式

There are multiple test cases.The first line of input contains a single integer TT denoting the number of test cases.
For each test case,there are 1010 lines in total.
The first 3∗23 \ast 2 lines describe the two triangles.Each line with two integers denotes the coordinates of a point.
The next 44 lines describe the quadrangle in clockwise order or counter-clockwise order.
All coordinates are less than 1500015000 in absolute value.

输出格式

For each test case,output Yes if the given triangles can form a quadrangle without overlapping,No otherwise.

2
0 0
0 1
1 0
0 0
0 1
1 0
-1 0
0 0
1 0
0 1
0 0
-1 1
1 0
0 0
0 1
1 0
-1 0
0 0
1 0
0 1
Case #1: Yes
Case #2: No

数据规模与约定

100%100\% 的数据满足:T≤500T \le 500。

题目来源

Acm 2011 上海