PROBLEM LINK:
Author: Roozbeh K
Tester: Roozbeh K
Editorialist: Roozbeh K
DIFFICULTY:
SIMPLE
PREREQUISITES:
Elementary vector geometry
PROBLEM:
In a game of Ultimate Frisbee, find the closest player to the other team’s end line and pass the frisbee to them.
QUICK EXPLANATION:
The team’s goal is to bring the frisbee to the other team’s end line as much as possible. The frisbee holder ideally wants to pass the frisbee to a player standing closest to the end line. But if an opponent is in the way, they have to settle for the next closest player. If all teammates are blocked, the team loses the frisbee (Turnover).
EXPLANATION:
This problem is about collinearity. There are only 10 points (each having name, x, and y coordinates) on the 2D plane (the court). Let’s say someone from team one holds the frisbee and wants to pass. They need to consider all other teammates for passing the frisbee starting with the ones having the greatest x coordinate value (closes to the end line). If two players are standing at the same x coordinates, then the frisbee goes to the player with the lexicographically greater name.
Just sort each team by their x coordinates and their name (in that order) and consider them one by one. To check if a player is blocked, the following formula can be used:
p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y) == 0
If p1, p2, and p3 are collinear, the above equality holds. We also need to make sure that the blocking opponent(p2) is actually between p1 and p3. This can be done by comparing the three points x and y coordinates and is a fairly straightforward task to accomplish.
Please note that if the second team holds the frisbee, we will need to sort the team array increasingly because the second team is playing towards the line x=0.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.