当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

1500:Polygonal Puzzle

题目描述
To help model the three dimensional volumes that describe each supercomputer choice over time, Valentine McKee and Jake Briggs decided to construct some cardboard mock-ups. Valentine began by cutting out polygons of each of the supercomputer criteria for each year. As she was bringing the cut-outs to Jake's lab, where they intended to turn the flat polygons into the actual volumes, Valentine bumped into Ren McCormack. Literally. And she dropped all of her polygon cut-outs onto the ground.
``Ren! Why don't you look where you're going,'' Valentine sighed. ``I dropped all of my polygons. Now I'm going to have to start all over cutting these out.'' Valentine had labeled the polygons prior to cutting them out, but unfortunately, the labeling was not part of the actual polygon and was lost when they were cut out. ``I don't know which is which now.''

``Sorry.'' Ren looked downcast, then brightened. ``Hey, do you want to go to the dance with me this weekend?''

``I don't think so, Ren,'' replied Valentine, ``I think I'll be cutting out and sorting polygons all weekend.'' Valentine stooped and began picking up the cut-outs. Ren was a great dancer but he also tended to show it off. The one time that Valentine had gone to a dance with him, Ren had completely embarrassed her with his antics.

``Can't you use a computer or something to help you sort those things out?'' Ren picked up one of the polygons and squinted at it. (Ren was a theater major.)

Valentine thought for a moment. ``Nope,'' she said. ``I'm just going to have to start over. Have fun at the dance this weekend, though.'' To herself, she thought, ``Yes, I can use a computer. The only other thing I need is that camera that Jake already has in the lab to help me see the Big Picture.''
输入解释
The first line of input will consist of two integers separated by a space. The first integer specifies the number of polygons to be sorted. The second integer specifies the number of vertices for each polygon.

The rest of the input will consist of two lists of coordinates. The first is a list of coordinates describing the shape of each polygon in terms of the values on each of its axes (i.e., the values for r1 through r6 in the figure below).

The vertices of each polygon are distributed at equal angles around the origin, with the first vertex aligned at 12 o'clock. The vertices are given in clockwise order. The polygons in this list are unique with respect to rotation and dilation. That is, no polygon will be exactly like any other polygon (having the same vertices in the same locations), nor can any polygon be rotated about its center and/or uniformly scaled such that it will be exactly like another polygon in the list.

The second list of polygon coordinates corresponds to the polygons in the first list, but as measured by a camera. The vertices of each polygon in this case will be given as (x, y) pairs with respect to the camera's viewpoint origin and are given in clockwise order. The first vertex given is arbitrary, however.

Note that the camera's view of each polygon may include magnification or de-magnification (which may be different for each viewed polygon). Moreover, the camera can only resolve the polygon vertices to within plus or minus one pixel in its field of view, so there may be some jitter associated with the viewed vertex locations. For each polygon, the maximum amount of jitter at each vertex is guaranteed to be less than one percent of the distance from the origin to the vertex farthest away from the origin.

All of the polygons viewed by the camera will be right-side up.

输出解释
The output is a list of instructions indicating how to rearrange the scrambled polygons. That is, for each polygon in the second list, the output should indicate the polygon to which it corresponds in the first list, the amount by which it must be rotated in a clockwise direction to align the vertices. Thus, one line of output consists of an integer index i (indexing starts from 1), a floating point angle (with ) given to the nearest tenth of a degree.
输入样例
2 4
1 1 2 1
1 1 1 1
1 3 2 3 2 2 1 2
2.5 3.5 2 2 1 2 1 3
输出样例
2 45.0
1 135.0

该题目是Virtual Judge题目,来自 北京大学POJ

源链接: POJ-1500

最后修改于 2020-10-29T06:05:46+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
1000 10000