{"id":34968,"date":"2024-11-01T09:34:07","date_gmt":"2024-11-01T09:34:07","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34968"},"modified":"2024-11-01T12:53:44","modified_gmt":"2024-11-01T12:53:44","slug":"%ec%bd%94%ed%8b%80%eb%a6%b0-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-%ea%b8%b0%ed%95%98-%ec%95%8c%ec%95%84%eb%b3%b4%ea%b8%b0-2","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34968\/","title":{"rendered":"Kotlin coding test course, exploring geometry"},"content":{"rendered":"

<\/p>\n

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

Problem Description<\/h2>\n

\nProblem:<\/strong> Given N points in a two-dimensional plane, output the coordinates of the points that form the convex hull in a clockwise manner.\n <\/p>\n

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

Input and Output Format<\/h2>\n

\nInput:<\/strong> The first line contains an integer N (1 \u2264 N \u2264 100,000),
\n followed by N lines where the x and y coordinates of each point are provided.
\n (x, y are integers that lie between -10^9 and 10^9.)\n <\/p>\n

\nOutput:<\/strong> Output the coordinates of the points that constitute the convex hull
\n in a clockwise manner, with each coordinate separated by a space.\n <\/p>\n

Problem-solving Process<\/h2>\n

\n To solve the problem, we need to go through the following steps:\n <\/p>\n

    \n
  1. \nInput Data Handling:<\/strong>
    \n Read the coordinates of the points and store them in a list.
    \n It is convenient to store each point as a Pair object.\n <\/li>\n
  2. \nSorting Coordinates:<\/strong>
    \n Sort the points based on polar angles.
    \n Use the leftmost bottom (or top) point as a reference and sort the remaining points based on polar angle.\n <\/li>\n
  3. \nGenerating Convex Hull:<\/strong>
    \n Use the Graham’s scan algorithm to find the points of the convex hull.\n <\/li>\n
  4. \nFormatting the Output:<\/strong>
    \n Organize the results in a clockwise manner and print them in the required format.\n <\/li>\n<\/ol>\n

    Code Implementation<\/h2>\n
    \n        \n            import kotlin.math.atan2\n            \n            data class Point(val x: Int, val y: Int)\n            \n            fun convexHull(points: List): List {\n                val sortedPoints = points.sortedWith(compareBy({ it.x }, { it.y }))\n                val hull = mutableListOf()\n                \n                \/\/ Lower part\n                for (point in sortedPoints) {\n                    while (hull.size >= 2 && cross(hull[hull.size - 2], hull[hull.size - 1], point) <= 0)\n                        hull.removeAt(hull.size - 1)\n                    hull.add(point)\n                }\n                \n                val lowerSize = hull.size\n                \n                \/\/ Upper part\n                for (i in sortedPoints.size - 1 downTo 0) {\n                    val point = sortedPoints[i]\n                    while (hull.size > lowerSize && cross(hull[hull.size - 2], hull[hull.size - 1], point) <= 0)\n                        hull.removeAt(hull.size - 1)\n                    hull.add(point)\n                }\n                \n                hull.removeAt(hull.size - 1) \/\/ Remove the last point because it is a duplicate\n                \n                return hull\n            }\n            \n            fun cross(o: Point, a: Point, b: Point): Int {\n                return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)\n            }\n            \n            fun main() {\n                val n = readLine()!!.toInt()\n                val points = List(n) {\n                    val (x, y) = readLine()!!.split(\" \").map { it.toInt() }\n                    Point(x, y)\n                }\n                val hull = convexHull(points)\n                hull.forEach { println(\"${it.x} ${it.y}\") }\n            }\n        <\/code>\n    <\/pre>\n
    Conclusion<\/h2>\n
    \n        In this post, we explained the problem of finding the convex hull.
    \n        Geometric problems are frequently found in actual coding assessments, so it is important
    \n        to practice sufficiently and solve various types of problems.
    \n        Additionally, enhance your problem-solving skills through other geometric challenges.\n    <\/p>\n
    Additional Learning Resources<\/h2>\n
    \n        If you want to learn Kotlin more deeply, I recommend the following resources:<\/p>\n