[Problem 4 | 1996 East-Central problem set | My ACM problem archive | my home page]

1996 Regional Programming Contest

"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 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.

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

Set 2 input, output

This page maintained by Ed Karrels.

Last updated November 25, 1997