Problem K
Drone Delivery
As head of engineering at Redwood Industries, a massive online retailer, you have recently been told by your top secret engineering team that drone delivery for your products can now be done! Excited, you bounce on this opportunity to test out the system, and see what can happen. In your first trial, you send out 40 drones to deliver packages, but all of the drones lost connection with the base, and ended up getting lost! After hours of brainstorming, you have devised a plan that you think will work: a connection system capable of sending messages through drones. Each drone acts as both a receiver and sender, so you can create chains of drones to send messages. Your goal is to set up the minimum number of connections, so each drone can talk to each other. For example if Drone A is closest to Drone B and Drone B is closest to Drone C, to send a message from A to C, you would go from A to B, then B to C. However, as the government is regulated airspace, the cost of setting up communication between two drones is directly proportional to the distance between the drones. Unfortunately, a big issue is that the drones are constantly making deliveries, so two drones that were close before, may not be close later. Therefore, you need to change your connections so that you, at all times, have the cheapest connection system, to keep the executives at Redwood Industries happy. As a result, your goal is to figure out the number of times that you will need to change connections.
You can assume that each drone moves linearly with a fixed velocity, and that no two drones will collide. Lastly, any communication network that becomes optimal at time $t > 0$ will be optimal for any time $v$, such that $t<v<t+10^{-6}$, where the initial optimal network is guaranteed to be unique.
Input
For each input, you can have multiple test cases. For each test case, the first line will contain the number of drones, $d$ ($2 \leq d \leq 50$). The next $d$ lines will contain the integers $a, b, c, v_ a, v_ b, v_ c$, where $a,b,c$ are the initial drone location ($-150 \leq a,b,c \leq 150$) and $d, e, f$ are the components of the drone’s velocity in km/h ($-100 \leq v_ a,v_ b,v_ c \leq 100$).
Output
For each test case display number of times communication system should be set up or changed.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 50 50 50 0 0 0 -15 -25 -35 0 0 0 |
1 |