TopCoder problem "Mirrors" used in TCI '02 Finals (Division I Level Three)



Problem Statement

    

A hall of mirrors is a large room with many mirrors throughout it. When you look at one of these mirrors, often you end up seeing an object that is far away and has been reflected off many mirrors. To aid in the design of halls of mirrors, you are to write a class Mirrors with a method seen, which will tell you what object is seen, given a particular configuration of mirrors and objects, and the location and direction being looked.

Your method will take a String[], mirrors, another String[], objects, and a int[], start. Each element of mirrors will be formatted as "<x1> <y1> <x2> <y2>", representing a mirror that starts at point (x1,y1) and ends at point (x2,y2). All mirrors are double sided. objects, will repesent all of the objects that are in the hall of mirrors and might be seen. Each element of objects will be formatted as "<name> <x> <y>", representing a circular object named <name>, centered at point (x,y) and with radius 1.

Finally, start will represent the location and direction that a person is looking from. The first element will be the x coordinate, the second element will be the y coordinate, and the third element will be the heading that they are looking in. The heading will be in the range 0 to 359, representing the number of degrees in a counter-clockwise direction, starting from straight right (positive x), that the person is looking. Thus a heading of 0 means the person is looking in the positive x direction, a heading of 90 indicates the positive y direction, and a heading of 45 indicates that the person is looking half way between the positive x and positive y directions.

Your method must determine what is seen when a person stands at the given coordinates and looks in the given direction. If the person sees himself, return "me". If the person doesn't see any object or himself, return "space". Otherwise return the name of the object the person sees.

 

Definition

    
Class:Mirrors
Method:seen
Parameters:String[], String[], int[]
Returns:String
Method signature:String seen(String[] mirrors, String[] objects, int[] start)
(be sure your method is public)
    
 

Notes

-All mirrors are double sided, and should be treated as line segments.
-All objects, and the person, are perfect circles and have a radius of 1.
-A mirror reflects light such that the angle formed between the mirror and the incoming light is the same as the angle formed between the mirror and the outgoing light. Thus the angle between the incoming and outgoing light is 180-2*(angle between mirror and light).
-If you look along a mirror, the mirror has no effect. (see examples).
 

Constraints

-Each element of mirrors will be formatted exactly as "<x1> <y1> <x2> <y2>", with no extra spaces.
-Each element of objects will be formatted exactly as "<name> <x> <y>", with no extra spaces or leading 0's.
-mirrors will contain between 0 and 50 elements, inclusive.
-objects will contain between 0 and 50 elements, inclusive.
-start will contain exactly three elements, the first two representing x and y, respectively, and the third representing the heading the person is looking in.
-All coordinates will be integers in the range 0 to 1000, inclusive.
-The heading (3rd element of start) will be in the range 0 to 359, inclusive.
-No objects or mirrors will overlap other objects, mirrors, or the person (this includes touching at one point).
-No element of mirrors will represent a point. (x1==x2 and y1==y2)
-Each object will have a unique <name> other than "me" or "space".
-Each <name> will contain only lowercase characters.
-To avoid cumulative rounding errors, the object (or "me" or "space") seen will be seen in 50 mirrors or less.
-To avoid rounding errors, the object seen will be seen definatively. This means that no objects will be barely seen, or almost seen, and there will never be any question about which mirror is seen. This is ensured by checking that the path to the object seen does not pass within 0.001 of any other object, mirror, or the person.
-Each element of mirrors, and objects will contain between 1 and 50 characters, inclusive.
 

Examples

0)
    
{"0 0 100 100"}
{"a 15 10"}
{10,5,90}
Returns: "a"
The one mirror is at a 45 degree angle
1)
    
{"0 0 100 100"}
{"a 15 10"}
{10,5,180}
Returns: "space"
2)
    
{"0 0 100 100"}
{"a 15 10"}
{20,5,135}
Returns: "a"
3)
    
{"0 0 0 1000","1000 0 999 1000"}
{"a 500 152"}
{2,0,1}
Returns: "a"
4)
    
{"10 0 20 0"}
{"a 30 0"}
{0,0,0}
Returns: "a"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1008

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4375&pm=1008

Writer:

lars2520

Testers:

Logan , zoidal , alexcchan , brett1479

Problem categories:

Geometry