# 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 => {