Skip to content

Hacker rank problem: Sherlock and Geometry

April 8, 2016

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:

  1. Area of a triangle using sides
  2. Shortest distance to line
  3. 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.
  4. 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 Output

YES
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
}

Advertisements

From → Uncategorized

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: