Assignment 9: Computational Geometry

1905 Expanding Rods (2)

• Hint: Binary search on the answer.

2653 Pick-up sticks (2)

• Hint: We are given that there are at most 1000 top sticks.

2318 TOYS (3)

• Hint: For each toy, find the leftmost cardboard (using binary search) that lies to the right of the toy.

2074 Line of Sight (4)

• Hint: Each obstacle induces a ‘‘shadow.’’

1696 Space Ant (4)

• Hint: Given the current point and the previous point, find how to find the next point just by using ccw.

2540 Hotter Colder (5)

• Hint: Intersection of half-planes.

1228 Grandpa's Estate (6)

1408 Fishnet (7)

1584 A Round Peg in a Ground Hole (7)

3525 Most Distant Point from the Sea (8, challenge problem)

• Hint: Binary seaerch on the answer.

3246 Game (9, challenge problem)

3266 Cow School (10, challenge problem)

• Note: This is an extremely hard problem. If you can't figure out why this is a geometry problem, don't even start coding.