Somewhere around the Mediterranean, a group of n Roman legionaries is fight- ing against n Carthaginian...

 

Transcribed Image Text:

Somewhere around the Mediterranean, a group of n Roman legionaries is fight- ing against n Carthaginian solders. Each Roman carries special arch, which can throw an arrow that kills the enemy immediately. The arrow goes in a stright line and stops when it hits the enemy. The Romans decide to pair off with the Carthaginians, forming n pairs, and then each Roman will shoot an arrow at his chosen enemy. Arrows cannot cross directions, so the Romans must choose no crossing lines to hit the enemy. Assume the position of each Roman legionary and each Carthaginian is a fixed point in the plane and no three positions are colinear. 1. Argue that there exists a line passing through one Roman and one Carthaginian such that the number of Romans on one side of the line equals the number of Carthaginians on the same side. Describe how to find such a line in O(n log n) time. 2. Give an O(n log n)-time algorithms to pair Romans with Carthaginians in such a way that no fire lines cross. Somewhere around the Mediterranean, a group of n Roman legionaries is fight- ing against n Carthaginian solders. Each Roman carries special arch, which can throw an arrow that kills the enemy immediately. The arrow goes in a stright line and stops when it hits the enemy. The Romans decide to pair off with the Carthaginians, forming n pairs, and then each Roman will shoot an arrow at his chosen enemy. Arrows cannot cross directions, so the Romans must choose no crossing lines to hit the enemy. Assume the position of each Roman legionary and each Carthaginian is a fixed point in the plane and no three positions are colinear. 1. Argue that there exists a line passing through one Roman and one Carthaginian such that the number of Romans on one side of the line equals the number of Carthaginians on the same side. Describe how to find such a line in O(n log n) time. 2. Give an O(n log n)-time algorithms to pair Romans with Carthaginians in such a way that no fire lines cross.