🔗 Full Problem 1004

The Little Prince lives on the asteroid B-664 for the sake of a rose he loves. One day, upon learning that the rose is in danger, the Little Prince sets off on a long journey along the galaxy to save the rose. However, the Little Prince's spaceship isn't in great shape, so he must travel while avoiding transitions between planetary systems as much as possible. The image below shows part of the galaxy map the Little Prince has unfolded.

The solid red line represents the path that minimizes the number of times the Little Prince must enter/exit planetary systems on his way from the starting point to the destination, and the circles represent the boundaries of the planetary systems. Multiple such paths may exist, but you can see that at least 3 entries/exits into planetary systems are required.

Given such a galaxy map, a starting point, and a destination, write a program to find the minimum number of planetary system entries/exits the Little Prince needs. (Assume that the boundaries of planetary systems never touch or cross each other. Also, the starting point or destination will never be given as lying exactly on a planetary system's boundary.)

The first line of the input gives the number of test cases T. For each subsequent test case, the first line gives the starting point $(x_1, y_1)$ and the destination $(x_2, y_2)$. The second line gives the number of planetary systems $n$, and over the following n lines, the center and radius $(c_x, c_y, r)$ of each planetary system are given. The input constraints are as follows: $(-1000 ≤ x_1, y_1, x_2, y_2, c_x, c_y ≤ 1000, 1 ≤ r ≤ 1000, 1 ≤ n ≤ 50)$

The coordinates and radii are all integers.

For each test case, print the minimum number of planetary system entries/exits the Little Prince must make.

• Input

TC
2
-5 1 12 1
7
1 1 8
-3 -1 1
2 2 2
5 5 1
-4 5 1
12 1 1
12 1 2
-5 1 5 1
1
0 0 2

• Output

TC
3
0

This seems like a problem that can be solved fairly easily by applying the content from problem 1002. In fact, I was able to solve it without looking up much of any reference.

Before solving the problem, there are a few things worth pointing out.
The numbers can make it easy to misread how each set of input is grouped.

Using the example above as a guide: the first number is the number of sets. In this case it's 2, meaning two sets are tested, so the result is printed on two lines.
After that, the data needed for the tests is printed.

-5 1 12 1 <= $x_1, y_1, x_2, y_2$
7 <= number of planets
1 1 8 <= $c_{x1}, c_{y1}, r_1$
-3 -1 1
2 2 2
5 5 1
-4 5 1
12 1 1
12 1 2 <= printed for the number of planets

Also, since the result is printed as the total combined count of entries/exits into planetary systems, there's no need to track entries and exits separately.

Since the problem's objective is to find the minimum number of planetary systems (hereafter circles) that must be passed through to get from the starting point to the destination, we only need to count the circles that must necessarily be passed through.
Whenever the starting point or destination is contained within a given circle, an entry/exit necessarily occurs. Therefore, counting the number of circles that fully contain the starting point or destination lets us compute the number of entries/exits.
There is one thing to be careful of: if a single circle contains both the starting point and the destination, it must be excluded from the count.
If a single circle contains both the starting point and the destination, movement happens entirely within that circle, so no entry/exit occurs.

The principle is simple. Calculate the distance between the circle's center and the point. If the calculated distance is shorter than the circle's radius, that circle contains the point.
This can be expressed as a formula as follows.

With the variables defined as in the table above, we can expand the formula for whether a circle contains a given point.

$$\sqrt{(x_0 - x)^2 + (y_0 - y)^2} < r$$

This is a relatively simple algorithm once the formula above is translated into code.

JAVA
import java.util.Scanner;

/**
 * Baekjoon Problem 1004 algorithm class
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/05/22/a1004">1004 solution</a>
 * @since 2021.04.24 Sat 02:15:31
 */
public class Main
{
	/**
	 * Main function
	 *
	 * @param args: [String[]] parameters
	 */
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		
		int length = scanner.nextInt();
		scanner.nextLine();
		
		for (int i = 0; i < length; i++)
		{
			String base = scanner.nextLine();
			
			int x_start = Integer.parseInt(base.split(" ")[0]);
			int y_start = Integer.parseInt(base.split(" ")[1]);
			
			int x_end = Integer.parseInt(base.split(" ")[2]);
			int y_end = Integer.parseInt(base.split(" ")[3]);
			
			int through = 0;
			
			int count = scanner.nextInt();
			scanner.nextLine();
			
			for (int j = 0; j < count; j++)
			{
				String circle = scanner.nextLine();
				
				int x = Integer.parseInt(circle.split(" ")[0]);
				int y = Integer.parseInt(circle.split(" ")[1]);
				int r = Integer.parseInt(circle.split(" ")[2]);
				
				boolean hasStartContain = hasContain(x_start, y_start, x, y, r);
				boolean hasEndContain = hasContain(x_end, y_end, x, y, r);
				
				// If this planet contains only one of the starting or destination points
				if (!(hasStartContain && hasEndContain) && (hasStartContain || hasEndContain))
				{
					through++;
				}
			}
			
			System.out.println(through);
		}
		
		scanner.close();
	}
	
	/**
	 * Function that returns whether the start/end point is contained
	 *
	 * @param xo: [int] x-coordinate of the start/end point
	 * @param yo: [int] y-coordinate of the start/end point
	 * @param x: [int] x-coordinate of the planet
	 * @param y: [int] y-coordinate of the planet
	 * @param r: [int] radius of the planet
	 *
	 * @return [boolean] whether the start/end point is contained
	 */
	private static boolean hasContain(int xo, int yo, int x, int y, int r)
	{
		return Math.sqrt(Math.pow(xo - x, 2) + Math.pow(yo - y, 2)) < r;
	}
}

• Geometry