Kotlin coding test course, exploring geometry

Geometry is utilized in many fields of computer science and is a frequently tested topic in coding assessments.
In this post, we will address a convex hull problem and explain how to solve it efficiently using Kotlin.

Problem Description

Problem: Given N points in a two-dimensional plane, output the coordinates of the points that form the convex hull in a clockwise manner.

A convex hull refers to the smallest convex polygon that encloses all points on a plane.
This problem is often posed in algorithm challenges, and efficient algorithms include Graham’s scan and Jarvis March.

Input and Output Format

Input: The first line contains an integer N (1 ≤ N ≤ 100,000),
followed by N lines where the x and y coordinates of each point are provided.
(x, y are integers that lie between -10^9 and 10^9.)

Output: Output the coordinates of the points that constitute the convex hull
in a clockwise manner, with each coordinate separated by a space.

Problem-solving Process

To solve the problem, we need to go through the following steps:

  1. Input Data Handling:
    Read the coordinates of the points and store them in a list.
    It is convenient to store each point as a Pair object.
  2. Sorting Coordinates:
    Sort the points based on polar angles.
    Use the leftmost bottom (or top) point as a reference and sort the remaining points based on polar angle.
  3. Generating Convex Hull:
    Use the Graham’s scan algorithm to find the points of the convex hull.
  4. Formatting the Output:
    Organize the results in a clockwise manner and print them in the required format.

Code Implementation

        
            import kotlin.math.atan2
            
            data class Point(val x: Int, val y: Int)
            
            fun convexHull(points: List): List {
                val sortedPoints = points.sortedWith(compareBy({ it.x }, { it.y }))
                val hull = mutableListOf()
                
                // Lower part
                for (point in sortedPoints) {
                    while (hull.size >= 2 && cross(hull[hull.size - 2], hull[hull.size - 1], point) <= 0)
                        hull.removeAt(hull.size - 1)
                    hull.add(point)
                }
                
                val lowerSize = hull.size
                
                // Upper part
                for (i in sortedPoints.size - 1 downTo 0) {
                    val point = sortedPoints[i]
                    while (hull.size > lowerSize && cross(hull[hull.size - 2], hull[hull.size - 1], point) <= 0)
                        hull.removeAt(hull.size - 1)
                    hull.add(point)
                }
                
                hull.removeAt(hull.size - 1) // Remove the last point because it is a duplicate
                
                return hull
            }
            
            fun cross(o: Point, a: Point, b: Point): Int {
                return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)
            }
            
            fun main() {
                val n = readLine()!!.toInt()
                val points = List(n) {
                    val (x, y) = readLine()!!.split(" ").map { it.toInt() }
                    Point(x, y)
                }
                val hull = convexHull(points)
                hull.forEach { println("${it.x} ${it.y}") }
            }

Conclusion

In this post, we explained the problem of finding the convex hull.
Geometric problems are frequently found in actual coding assessments, so it is important
to practice sufficiently and solve various types of problems.
Additionally, enhance your problem-solving skills through other geometric challenges.

Additional Learning Resources

If you want to learn Kotlin more deeply, I recommend the following resources:

Good luck with your coding test preparation and I hope for positive results!