# 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.

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,Â xiÂ yi, ofÂ ithÂ 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 <= 104
• 0 <= xi, yiÂ <= 104
• 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 => {