[Kotlin] Korean Coding Test - Programmers - Billiard Practice

Question

Link

Muschuk, the mascot of Programmers, recently started playing billiards as a hobby.

My billiard teacher told me that I was at a billiard academy today"One Cushion" (It's called a cushion to hit the ball against the wall in billiards, and if you hit the ball once on the wall, it's called a one-cushion), he gave me a list containing the location of the billiard ball. The list contains the positions of the balls that awkwardness has to hit. You can practice "one cushion" by placing the ball in order at each position on the list. At this time, the awkward always puts the ball in the same position and hits it to hit the ball in the listed position.

Unlike Muschuk, you, who recently started solving algorithm problems as a hobby, wondered how far at least you had to roll until Muschuk hit one ball for each target.

Two integers, startX and startY, representing the horizontal and vertical lengths of the billiard table m, n, and the positional coordinates of the ball to be hit by the awkward, and two-dimensional integer array balls containing the positional coordinates of the balls to be given. For "One Cushion" practice, complete the solution function to return the square of the minimum value of the distance the ball hit by the ball in an array each time when the ball hits the target ball after hitting it at least once.

However, when the ball hit the wall, the direction of progress is always the same as the angle of incidence and reflection, and if it hits the vertex, the ball proceeds in the opposite direction of entry. Ignore the size of the ball and determine that the two balls hit each other only if the coordinates of the two balls match exactly. The ball does not stop before it hits the target ball, and it is assumed that it stops immediately when it hits the target ball.

Restrictions

3 ≤ m, n ≤ 1,000

0 < startX < m

0 < startY < n

2 ≤ balls length ≤ 1,000

• The elements of balls are in the form of [a, b].
• a, b means the coordinates on which the ball is placed that the awkward has to hit.
• 0 < a < m, 0 < b < n
• Inputs that are (a, b) = (startX, startY) are not received.

Input/Output Example

Input

• m: 10
• n: 10
• startX: 4
• startY: 7
• balls:  [[7, 7], [2, 7], [7, 3]]

Output: [52, 37, 116]

Solve

Draw a triangle using point symmetry. The diagonal length is the distance the ball rolled.

down, up

right, left

Code

class Solution {

    fun solution(m: Int, n: Int, startX: Int, startY: Int, balls: Array<IntArray>): IntArray {
        val answer = ArrayList<Int>()
        for (i in balls.indices) answer.add(getMinDistance(m, n, startX, startY, balls[i]))
        return answer.toIntArray()
    }

    /**
     * Find the minimum distance
     * - Draw a triangle in all directions, up, down, left, and right to obtain the minimum distance.
     * - Except where the X or Y coordinates are the same.
     */
    private fun getMinDistance(width: Int, height: Int, startX: Int, startY: Int, ball: IntArray): Int {
        var min = Integer.MAX_VALUE
        // Draw a triangle in a downward direction. Except when the target ball is below the same X axis.
        if (!(ball[0] == startX && ball[1] < startY))
            min = minOf(min, calculateSlopeSquareRoot(startX, startY, ball[0], ball[1] * -1))
        // Draw a triangle upward. Except when the target ball is on the same X axis.
        if (!(ball[0] == startX && ball[1] > startY))
            min = minOf(min, calculateSlopeSquareRoot(startX, startY, ball[0], 2 * height - ball[1]))
        // Draw a triangle in the left direction.
        // Except when the target ball is on the left side of the same Y axis.
        if (!(ball[1] == startY && ball[0] < startX))
            min = minOf(min, calculateSlopeSquareRoot(startX, startY, ball[0] * -1, ball[1]))
        // Draw a triangle in the right direction.
        // Except when the target ball is to the right of the same Y-axis.
        if (!(ball[1] == startY && ball[0] > startX))
            min = minOf(min, calculateSlopeSquareRoot(startX, startY, 2 * width - ball[0], ball[1]))
        return min
    }

    /**
     * Calculate the square root of the slope
     * - Diagonal ^2 = Horizontal ^2 + Vertical ^2
     */
    private fun calculateSlopeSquareRoot(startX: Int, startY: Int, targetX: Int, targetY: Int): Int {
        // There doesn't seem to be much difference from the speed at which kotlin.math.pow is used
        val diffX = startX - targetX
        val diffY = startY - targetY
        return diffX * diffX + diffY * diffY
    }

}

TEST 1 〉	Pass (8.88ms, 62.2MB)
TEST 2 〉	Pass (6.64ms, 62MB)
TEST 3 〉	Pass (6.28ms, 60.8MB)
TEST 4 〉	Pass (6.41ms, 62.3MB)
TEST 5 〉	Pass (8.59ms, 61.7MB)
TEST 6 〉	Pass (9.45ms, 62.6MB)
TEST 7 〉	Pass (6.71ms, 61.7MB)
TEST 8 〉	Pass (8.41ms, 60.6MB)
TEST 9 〉	Pass (6.40ms, 61.3MB)
TEST 10 〉	Pass (8.83ms, 62.5MB)
TEST 11 〉	Pass (8.15ms, 61.9MB)
TEST 12 〉	Pass (10.32ms, 60.2MB)
TEST 13 〉	Pass (9.62ms, 61.8MB)
TEST 14 〉	Pass (7.74ms, 62.2MB)
TEST 15 〉	Pass (5.85ms, 62.1MB)
TEST 16 〉	Pass (6.16ms, 62MB)
TEST 17 〉	Pass (7.07ms, 63.2MB)
TEST 18 〉	Pass (7.62ms, 61.8MB)
TEST 19 〉	Pass (5.99ms, 62MB)
TEST 20 〉	Pass (7.50ms, 61.4MB)
TEST 21 〉	Pass (8.75ms, 62.7MB)
TEST 22 〉	Pass (8.80ms, 62.1MB)
TEST 23 〉	Pass (8.20ms, 60.7MB)
TEST 24 〉	Pass (7.71ms, 62.9MB)
TEST 25 〉	Pass (6.34ms, 62.3MB)
TEST 26 〉	Pass (6.18ms, 61.8MB)
TEST 27 〉	Pass (7.95ms, 61.3MB)
TEST 28 〉	Pass (9.28ms, 61.6MB)
TEST 29 〉	Pass (8.58ms, 60.9MB)
TEST 30 〉	Pass (7.30ms, 59.9MB)
TEST 31 〉	Pass (8.80ms, 61.7MB)
TEST 32 〉	Pass (9.68ms, 62.2MB)
TEST 33 〉	Pass (5.60ms, 61.6MB)
TEST 34 〉	Pass (14.56ms, 62.1MB)
TEST 35 〉	Pass (5.96ms, 62.5MB)
TEST 36 〉	Pass (8.47ms, 62.4MB)