#icpc2013summerday4g. [icpc2013summer_day4_g]Spotlight Movement

[icpc2013summer_day4_g]Spotlight Movement

问题陈述

Ciel是一位外貌和行为类似狐狸的偶像,他正在参加几天后即将举行的现场音乐会的彩排。要成为一名顶级偶像,需要付出大量努力!

现场舞台可以用一个二维平面来表示。现场舞台有NN个聚光灯以照亮舞台。第ii个聚光灯投射的光线范围为一个半径为rir_{i}的圆。第ii个聚光灯所投射的光线沿着轨道RiR_i移动。轨道RiR_i是一个封闭多边形,虽然RiR_i可能包含自交点。聚光灯从RiR_i的第一个顶点开始移动。每个聚光灯的轨道周期相同。每个聚光灯以恒定的速度移动,并且它们同时回到起点。

在彩排中,Ciel必须从起点移动到舞台上标示的终点。为了实现她的目标,不允许她离开受聚光灯照亮的区域。但是,只要她站在起点上,她就不必被聚光灯照亮。你可以假设她移动的速度足够快。回答是否有可能让她移动到终点。


输入

每个输入数据集以以下格式给出:

NN sxsx sysy exex eyey r1r_{1} K1K_{1} x11x_{11} y11y_{11} x12x_{12} y12y_{12} ... x1K1x_{1K_{1}} y1K1y_{1K_{1}} r2r_{2} K2K_{2} x21x_{21} y21y_{21} x22x_{22} y22y_{22} ... x2K2x_{2K_{2}} y2K2y_{2K_{2}} : : rNr_{N} KNK_{N} xN1x_{N1} yN1y_{N1} xN2x_{N2} yN2y_{N2} ... xNKNx_{NK_{N}} yNKNy_{NK_{N}}

所有的输入都是整数。所有的坐标信息满足\-10,000x\-10,000 \leq x, y10,000y \leq 10,000NN (1N1001 \leq N \leq 100)表示聚光灯的数量。(sx,sy)(sx, sy)(ex,ey)(ex, ey)分别表示Ciel路径的起点和终点。以下的NN行表示每个聚光灯的信息。rir_{i} (1ri1001 \leq r_{i} \leq 100)表示聚光灯的半径。KiK_{i} (2Ki102 \leq K_{i} \leq 10)表示轨道路径上的顶点数。然后,给出KiK_{i}个顶点。同一个轨道路径上的两个连续顶点位于不同的位置。聚光灯从第一个点(xi1,yi1)(x_{i1}, y_{i1})移动到第二个点(xi2,yi2)(x_{i2}, y_{i2}),然后移动到第三个点(xi3,yi3)(x_{i3}, y_{i3}),以此类推。移动到第KiK_{i}个点(xiKi,yiKi)(x_{iK_{i}}, y_{iK_{i}})之后,聚光灯返回到第一个点(xi1,yi1)(x_{i1}, y_{i1})并重新开始移动。

dijd_{ij}是聚光灯ii和聚光灯jj之间最近的中心点之间的距离。dijd_{ij}满足以下两种情况之一:

  • dij>ri+rj+0.000001d_{ij} > r_{i} + r_{j} + 0.000001

  • dij<ri+rj0.000001d_{ij} < r_{i} + r_{j} - 0.000001

另外,设did_{i}是聚光灯ii的中心点与起点或终点之间的最短距离。did_{i}满足以下两种情况之一:

  • di>ri+0.000001d_{i} > r_{i} + 0.000001

  • di<ri0.000001d_{i} < r_{i} - 0.000001

输出

如果Ciel可以在不离开照亮区域的情况下将终点移动到,则输出Yes。否则,输出No


示例输入1

2 1 1 9 -1
2 2 1 1 -9 1
1 2 -1 -1 9 -1

示例输出1

Yes

示例输入2

2 1 1 9 -1
2 2 1 1 -9 1
1 2 9 -1 -1 -1

示例输出2

No

示例输入3

2 11 6 -9 1
6 4 10 5 10 0 5 0 5 5
5 4 -10 0 -10 5 -5 5 -5 0

示例输出3

Yes

示例输入4

1 1 9999 -1 0
100 2 0 0 0 10000

示例输出4

Yes

数据来源

Summer Camp 2013