# Hacker rank problem: Sherlock and Geometry

Had fun solving this problem yesterday evening & today got accepted after minor fixes.

https://www.hackerrank.com/challenges/sherlock-and-geometry

Solving these kind of algorithm design problems, gives me a kind of a high. And I want to shout out, to anybody who may be interested! 🙂 [PS: If you land here via search engine, in search of a solution. You can sure refer, but please don’t cheat]. No high, like writing your own code. And once you see all the test cases passing, and full marks (in this case 60) being awarded, you are one very happy programmer.

I am too lazy to explain the design. So just dumping the code below. Some helpful comments are there, though. Some concepts, I have made use of, in brief:

- Area of a triangle using sides
- Shortest distance to line
- Checking if the shortest distance to a line, happens to be the shortest distance to that line segment. If yes, then just checking if its less than radius. If no, then the segment is outside.
- Also some simple checks upfront like if the triangle is inside the circle, fully. Or if triangle has points lying on either side of the circle perimeter.

‘Nuff said. Code is below:

/**

https://www.hackerrank.com/challenges/sherlock-and-geometry

Watson gives a circle and a triangle in a 2-dimensional plane to Sherlock. Sherlock has to tell if they intersect/touch each other.

The circle is centered at (xc,yc)(xc,yc) and has radius RR.Input Format

The first line contains TT, the number of test cases.

Each test case consists of xcxc, ycyc and RR in one line.

The next three lines each contains xi,yixi,yi denoting the vertices of the triangle.Output Format

For each test case, print YES if the triangle touches or intersects the circle; otherwise, print NO.Constraints

1≤T≤300001≤T≤30000

1≤R≤20001≤R≤2000

−2000≤xc,yc≤2000−2000≤xc,yc≤2000

−5000≤xi,yi≤5000−5000≤xi,yi≤5000

Note: There will be no degenerate triangles (i.e. triangles with area 0)Sample Input

2

0 0 10

10 0

15 0

15 5

0 0 10

0 0

5 0

5 5

Sample OutputYES

NO**/

package main

import (

//”bufio”

“fmt”

“math”

//”os”

//”sort”

// “strconv”

//”strings”

)func main() {

var T int

fmt.Scan(&T)

//fmt.Printf(“T = %v\n”, T)for t := 0; t < T; t++ {

// circle

var x, y, ri int

fmt.Scan(&x)

fmt.Scan(&y)

fmt.Scan(&ri)

//fmt.Printf(“%v, %v, %v\n”, x, y, ri)// 3 points of triangle

var x1, y1, x2, y2, x3, y3 int

fmt.Scan(&x1)

fmt.Scan(&y1)

fmt.Scan(&x2)

fmt.Scan(&y2)

fmt.Scan(&x3)

fmt.Scan(&y3)

//fmt.Printf(“%v, %v; %v, %v; %v, %v\n”, x1, y1, x2, y2, x3, y3)p1_d := dist(x, y, x1, y1)

p2_d := dist(x, y, x2, y2)

p3_d := dist(x, y, x3, y3)

//fmt.Printf(“%v, %v, %v\n”, p1_d, p2_d, p3_d)r := float64(ri)

if p1_d < r && p2_d < r && p3_d < r {

// all points inside circle

fmt.Printf(“NO\n”)

} else if atleastTwoPointsOtherSide(p1_d, p2_d, p3_d, r) {

// at least 1 point inside with at least 1 outside

fmt.Printf(“YES\n”)

} else {

// all outside// looking at the min distance of each side

// from circle center

if checkDistToLineSegment(ri, x, y, x1, y1, x2, y2) {

fmt.Printf(“YES\n”)

} else if checkDistToLineSegment(ri, x, y, x2, y2, x3, y3) {

fmt.Printf(“YES\n”)

} else if checkDistToLineSegment(ri, x, y, x1, y1, x3, y3) {

fmt.Printf(“YES\n”)

} else {

fmt.Printf(“NO\n”)

}}

}

}func dist(x1, y1, x2, y2 int) float64 {

x := x2 – x1

y := y2 – y1

sum := x*x + y*y

return math.Sqrt(float64(sum))

}// if dist of at least one point is less than r

// and dist of at least one point is greater than r

func atleastTwoPointsOtherSide(p1, p2, p3, r float64) bool {

if p1 <= r {

if p2 >= r || p3 >= r {

return true

}

} else {

if p2 <= r || p3 <= r {

return true

}

}if p2 <= r {

if p1 >= r || p3 >= r {

return true

}

} else {

if p1 <= r || p3 <= r {

return true

}

}if p3 <= r {

if p2 >= r || p1 >= r {

return true

}

} else {

if p2 <= r || p1 <= r {

return true

}

}return false

}func areaBasedOnSides(a, b, c float64) float64 {

s := (a + b + c) / 2.0

return math.Sqrt(s * (s – a) * (s – b) * (s – c))

}// center x,y with a line segment of the triangle

// in this we check if shortest dist to line segment,

// is also the shortest distance to line

// if so returns true

// else false

func checkDistToLineSegment(r, x, y, x1, y1, x2, y2 int) bool {

a := dist(x1, y1, x2, y2)

b := dist(x, y, x1, y1)

c := dist(x, y, x2, y2)

A := areaBasedOnSides(a, b, c)

//fmt.Printf(“A: %v\n”, A)// shortest distance to line

h := (2 * A) / a

//fmt.Printf(“h: %v\n”, h)// Check if shortest distance to line, falls in line segment

hi := int(h * 100)

if hi <= r*100 {

theta1 := math.Asin(h / b)

theta2 := math.Asin(h / c)a1 := b * math.Cos(theta1)

a2 := c * math.Cos(theta2)if a1 > a || a2 > a {

// approximately (a1+a2) should be equal to a

// but if a single part is greater means the perpendicular meets much outside the

// line segment

return false

} else {

return true

}

}return false

}