Convex Hull – HackerRank Solution

In this post, we will solve Convex Hull HackerRank Solution. This problem (Convex Hull) is a part of HackerRank Functional Programming series.

Problem

Convex Hull of a set of points, in 2D plane, is a convex polygon with minimum area such that each point lies either on the boundary of polygon or inside it.

Let’s consider a 2D plane, where we plug pegs at the points mentioned. We enclose all the pegs with a elastic band and then release it to take its shape. The closed structure formed by elastic band is similar to that of convex hull.

Tasks

Given a set of N points, Find the perimeter of the convex hull for the points.

Input Format

First line of input will contain a integer, N, number of points. Then follow N lines where each line contains the coordinate, x_i y_i, of i^th point.

Output Format

Print the perimeter of convex hull for the given set of points. An error margin of +/- 0.2 is acceptable.

Constraints

• 3 <= N <= 10⁴
• 0 <= x_i, y_i <= 10⁴
• There exists, at least, three points which are non-colinear.

Sample Input

6    
1 1    
2 5    
3 3    
5 3    
3 2    
2 2

Sample Output

12.2   

Explanation

For the given set of points in sample input, the convex hull is formed by the triangle whose vertices are given by (1, 1), (2, 5), (5, 3). Here perimeter of the hull is 12.200792856.

Solution – Convex Hull

Scala

import java.util.Scanner

import scala.collection.mutable

object Orientation extends Enumeration {
  type Orientation = Value
  val Collinear, Clockwise, Counterclockwise = Value
}

object Solution {

  import Orientation.Orientation

  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)
    val n = sc.nextInt

    case class Point(x: Int, y: Int)

    val initialPoints = (0 until n).map(_ => Point(sc.nextInt, sc.nextInt))

    val bottommostIndex = initialPoints.indices.reduce((accIndex, pIndex) => {
      val acc = initialPoints(accIndex)
      val p = initialPoints(pIndex)
      if (acc.y < p.y || acc.y == p.y && acc.x < p.x) accIndex else pIndex
    })

    val basePoint = initialPoints(bottommostIndex)

    def polarAngle(point: Point) = math.atan2(point.y - basePoint.y, point.x - basePoint.x)

    def distance2(p0: Point, p1: Point) = {
      val dx = p1.x - p0.x
      val dy = p1.y - p0.y

      dx * dx + dy * dy
    }

    def distance(p0: Point, p1: Point) = math.sqrt(distance2(p0, p1))

    val points = initialPoints.indices.filter(_ != bottommostIndex).map(initialPoints(_))
      .sortWith((p0, p1) => {
        val polar0 = polarAngle(p0)
        val polar1 = polarAngle(p1)

        polar0 < polar1 || polar0 == polar1 && distance2(p0, basePoint) < distance2(p1, basePoint)
      })
      .toList

    def filterSameAngle(points: List[Point]): List[Point] = points match {
      case a :: b :: xs =>
        if (polarAngle(a) == polarAngle(b))
          filterSameAngle(b :: xs)
        else
          a :: filterSameAngle(b :: xs)
      case list => list
    }

    val filteredPoints = basePoint :: filterSameAngle(points)

    val orderedCount = 3
    val stack = mutable.Stack[Point]()
    stack.pushAll(filteredPoints.take(orderedCount))

    def orientation(p0: Point, p1: Point, p2: Point): Orientation = {
      val cross = (p1.y - p0.y) * (p2.x - p1.x) - (p1.x - p0.x) * (p2.y - p1.y)

      if (cross == 0) Orientation.Collinear else if (cross > 0) Orientation.Clockwise else Orientation.Counterclockwise
    }

    filteredPoints.drop(orderedCount)
      .foreach(p => {
        while (orientation(stack.tail.head, stack.head, p) != Orientation.Counterclockwise)
          stack.pop()
        stack.push(p)
      })

    println((stack.toList :+ stack.head).sliding(2)
      .map(list => distance(list.head, list.last))
      .sum)
  }
}

Note: This problem (Convex Hull) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.