SCHOOL OF COMPUTER SCIENCE

Crush the Rebellion

Ten rebel encampments have sprung up on the plane of Usyan. The Martian Federation plans to send flying saucers to deal with them. They are pretty ruthless. They will simply land on top of the encampments. The encampments are small and the saucers are huge. It must be done simultaneously, or the rebels will flee. Also, the saucers must not overlap when they land. Can the Martians prevail?

Mathematically the encampments are points in the plane and the saucers are non-overlapping disks of equal radius.

 

alanATrandomDOTmathDOTcmuDOTedu

Solution