题目 1958:
时间限制: 1s
内存限制: 128MB
蓝桥杯算法提高VIP-Eyeball Benders
题目描述
"眼球风暴"是当下非常流行的一个游戏。在这个游戏中，玩家需要从一张近视图中识别出图中的物体是什么。比如，一张看起来像是锥形蜡笔的图可能是一个新开的蜡笔盒的图的一部分。下图展示了一个例子，左边的是给出的谜题，而右边则是解答。
图1，一个“眼球风暴”的给出的谜题和解答。（软盘）
你需要做的事是检验一个简化的“眼球风暴”的问题。我们会给你两张图，每张图都是一些线段的集合，且每条线段都是垂直于坐标轴的，并且每条线段都包括它的两个端点。
你需要确定第一张图是不是第二张图的某个部分的放大图。所有的线段都被认为是无宽度的。你需要保证，在第一张图中某条线段的端点在放大前一定是第二张图中某条线段的端点。
图2，第一张图是第二张图中画虚线区域放大三倍后的图。
坐标的单位和比例在同一张图内是一样的。一张图内的单位和比例不一定和另外一张图是一样的。第一张图的大小至少应该是原图中该部分的1倍。对于图2，你应该判定第一张图是第二张图的一部分。
图1，一个“眼球风暴”的给出的谜题和解答。（软盘）
你需要做的事是检验一个简化的“眼球风暴”的问题。我们会给你两张图，每张图都是一些线段的集合，且每条线段都是垂直于坐标轴的，并且每条线段都包括它的两个端点。
你需要确定第一张图是不是第二张图的某个部分的放大图。所有的线段都被认为是无宽度的。你需要保证，在第一张图中某条线段的端点在放大前一定是第二张图中某条线段的端点。
图2，第一张图是第二张图中画虚线区域放大三倍后的图。
坐标的单位和比例在同一张图内是一样的。一张图内的单位和比例不一定和另外一张图是一样的。第一张图的大小至少应该是原图中该部分的1倍。对于图2，你应该判定第一张图是第二张图的一部分。
输入格式
第一行有两个整数N、M，分别代表第一张图中的线段数量和第二张图中的线段数量。
接下来4*(N+M)个实数，每四个数分别代表一条线段的两个端点的坐标。前4*N个实数代表第一张图的N条线段，剩下的数代表第二张图的M条线段。所有的实数不会超过三位小数。所有的线段长度至少为0.005，线段之间不会覆盖只会相交。数据保证给出的N条线段不同向的线段间至少有一个交点。
接下来4*(N+M)个实数，每四个数分别代表一条线段的两个端点的坐标。前4*N个实数代表第一张图的N条线段，剩下的数代表第二张图的M条线段。所有的实数不会超过三位小数。所有的线段长度至少为0.005，线段之间不会覆盖只会相交。数据保证给出的N条线段不同向的线段间至少有一个交点。
输出格式
如果第一张图能够在第二张图中找到并且满足上述所有要求，那么输出“valid puzzle”，否则输出“impossible”。数据保证如果第一张图在第二张图中能够被找到，那么不被包括在答案矩形中的线段至少距离矩形0.005。
样例输入
3 12 9 8 7.5 8 1.5 8 1.5 3.5 0 5 9 5 4 2 8 2 5 7 2 7 10 6 8 6 8 7 8 4 1 9 8 9 9 3 7 3 4 10 4 5 4 2 4 4 5 8 5 7 3 6 6 6 0 3 3 3 5 1 5 3
样例输出
valid puzzle
标签