P1222

Split

Split

平面上给出两个简单多边形，即边仅在相邻顶点处相交且不自交。每个多边形的顶点均按边界顺序给出，顺时针或逆时针均可。

两个多边形可以进行任意平移和旋转，但不能翻转。请判断是否存在一种放置方式，使两个多边形的内部没有公共点，并且拼接后组成一个凸多边形。

输入格式

输入包含多组测试数据，每组数据的格式如下：

  • 第一行包含一个整数 N1N_1，表示第一个多边形的顶点数；
  • 接下来 N1N_1 行，每行包含两个实数 xx 和 yy，表示第一个多边形的一个顶点坐标，顶点按边界顺序给出；
  • 接下来一行包含一个整数 N2N_2，表示第二个多边形的顶点数；
  • 接下来 N2N_2 行，每行包含两个实数 xx 和 yy，表示第二个多边形的一个顶点坐标，顶点按边界顺序给出。

输入以文件结束符（EOF）终止。

输出格式

对于每组测试数据：

  • 如果可以通过平移和旋转，且不翻转两个多边形，使它们在内部没有公共点的情况下拼接成一个凸多边形，则输出 1；
  • 否则输出 0。

判定过程中，若两条边的长度之差的绝对值不超过 10−610^{-6}，则认为它们等长；若两个角之和与 π\pi 的差的绝对值不超过 10−710^{-7}，则认为它们互补。所有几何判定均按照上述容差进行。

样例输入

4
0 0
0 1
1 1
1 0
4
0 0
0 1
1 1
1 0
4
0 0
0 1
1 1
1 0
4
0 0
0 1
1 1
1 0

样例输出

1
1

数据范围

  • 3≤N1≤103\le N_1\le 10；
  • 3≤N2≤103\le N_2\le 10；
  • 所有坐标均为实数，且坐标绝对值不超过 10410^4；
  • 坐标的小数部分最多保留 1010 位；
  • 每个多边形均为非退化多边形，面积严格大于 00；
  • 任意两个相邻顶点之间的欧几里得距离严格大于 10−510^{-5}；
  • 不存在连续三点共线，即任意三个连续顶点构成的有向角的绝对值严格大于 10−610^{-6}；
  • 所有顶点互不相同，任意两点之间的距离严格大于 10−610^{-6}；
  • 每个多边形的有向面积的绝对值严格大于 10−710^{-7}。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

4
0 0
0 1
1 1
1 0
4
0 0
0 1
1 1
1 0
4
0 0
0 1
1 1
1 0
4
0 0
0 1
1 1
1 0

输出

1
1