# Concave Polygon – HackerRank Solution

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

You are given the cartesian coordinates of a set of points in aÂ 2DÂ plane (in no particular order). Each of these points is a corner point of some Polygon,Â P, which is not self-intersecting in nature. Can you determine whether or notÂ PÂ is aÂ concave polygon?

## Input Format

The first line contains an integer,Â N, denoting the number of points.
TheÂ NÂ subsequent lines each containÂ 2Â space-separated integers denoting the respectiveÂ xÂ andÂ yÂ coordinates of a point.

## Constraints

• 3 <= N <= 1000
• 0 <= x, y <= 1000

## Output Format

PrintÂ YESÂ ifÂ PÂ is a concave polygon; otherwise, printÂ NO.

Sample Input

``````4
0 0
0 1
1 1
1 0``````

Sample Output

``NO``

Explanation

The given polygon is a square, and each of itsÂ 4Â internal angles areÂ 90. As none of these are overÂ 180, the polygon isÂ notÂ concave and we printÂ NO.

Scoring

The percentage score awarded for your submission will be:

``    100 - 2*(percentage of tests which you solve incorrectly)  ``

If this value is negative, the percentage score for your submission will be 0.
So if you get half or more of the tests incorrect, your score will be a zero.

## Solution – Concave Polygon – HackerRank Solution

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
}

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

val filteredPoints = basePoint :: 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 => {