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.

Task

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 => {
        while (orientation(stack.tail.head, stack.head, p) != Orientation.Counterclockwise)
          stack.pop()
        stack.push(p)
      })

    println(if (stack.size == n) "NO" else "YES")
  }
}

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