Problem A
Eyeball Benders
Input File: eyeball.in
“Eyeball benders” are a popular kind of puzzle in which the reader must identify a common object based on a close-
up view of a part of that object. For instance, an image that looks like a regular array of colored cones might be a
view of an open box of new crayons. Figure 1 shows an example where the puzzle is on the left and the solution is
on the right.
Figure 1. A sample eyeball-bender puzzle and solution image (a floppy disk).
You must verify solutions to a simplified version of the “eyeball bender” puzzle. You will be given a number of
pairs of images, each one a collection of line segments. All line segments will be either horizontal or vertical, and
they include their endpoints. Figure 2 shows an example.
You must determine whether the images form a valid pair in which the first image is a magnified view of some
portion of the second image. Lines are assumed to have zero thickness in both images. At least one endpoint in the
puzzle image of a valid pair must be an endpoint of a line segment in the solution image.
Figure 2. The left image is the portion of the right image inside the dotted rectangle, magnified 3 times.
Coordinates describe relative positions and scale within a single image. The coordinates in one image do not
necessarily use the same origin or scale as those in the other image. The magnification of the puzzle image relative
to the solution image is required to be greater than or equal to 1. For Figure 2, your program should determine that
this is a valid puzzle/solution image pair.
0
0
(
9
,
8
)
(
9
,
5
)
10
10
0
(1.5,3.5)
(1.5,8)
(7.5,8)
(
0
,
5
)
0
10
10
(
0
,
3
)
(
3
,
3
)
(
4
,
2
)
(5,1)
(5,3)
(
7
,
3
)
(9,3)
(
8
,
4
)
(8,2)
(3,6)
(6,6)
(2,7)
(5,7)
(5,8)
(1,9)
(8,9)
(8,7)
(8,6)
(
4
,
4
)
(
4
,
5
)
(4,10)
(10,6)