18
3
You are the captain of a battleship. The engineering department's been cutting corners with designs this year, so the ship you're on takes the shape of a simple triangle.
You walk out onto the deck and enjoy the sea breeze... though not for long. An enemy has fired at you! — but will the shot hit?
Input
You may write either a function or a full program for this challenge.
Your program will take in 11 integers, ten of which are paired:
The first three pairs of integers (x1, y1), (x2, y2), (x3, y3) will specify the vertices of your ship. The triangle formed will have nonzero area.
The next pair of integers (ex, ey) specifies the location of the enemy's cannon. The enemy cannon will never lie on, or within the boundary of your ship.*
The pair (ax, ay) after that specifies where the enemy aimed at. This will be distinct from (ex, ey).
The final positive integer R specifies the range of the enemy's shot
*You'd be a terrible captain if you didn't even notice that happening!
Output
You must print/return a truthy value (e.g. true, 1) if the battleship will be hit, otherwise a falsy value (e.g. false, 0).
What is a hit?
The enemy shot is a straight line segment of length R from (ex, ey) in the direction of (ax, ay). If this line segment overlaps any part of the interior of your triangular battleship, then this counts as a hit. Otherwise it is not a hit.
Shots which graze along or only reach up to the boundary of the triangle do not count as a hit.
Examples
0 0 0 1 1 0
1 1
0 0
2
Hit: The enemy has shot right through the centre of your ship!
2 0 0 2 4 4
0 0
1 1
1
No hit: The enemy's range is too short, so you are safe.
0 0 1 2 3 0
-4 0
0 0
8
No hit: The enemy has grazed the side of your ship, so this does not count as a hit. Lucky!
0 0 -1 3 4 -1
-3 -4
3 4
5
No hit: The enemy shot just stops short of the ship, so you are safe. If the enemy's cannon had even slightly better range, then you would have been hit! Phew!
-2 -3 -3 6 7 -2
-6 2
1 -4
7
Hit: Even though the shot didn't penetrate to the other side, this is still a hit.
-3 2 2 -4 7 -3
-3 -4
-3 0
10
No hit: For the record, this is another close miss.
Additional test cases
0 0 6 0 6 8
-6 -8
6 8
20
No hit: This is another graze, but at an angle.
0 0 -2 -5 5 3
-3 4
0 0
6
Hit: The shot entered via a vertex of the ship.
Scoring
This is code-golf, so the shortest code in bytes wins. Standard loopholes apply.
Just to make sure we can't: can we assume the ship has no bottom and that there's a tiny gap between each two sides, so that if the shot manages to enter the ship through its corner, we count it as a miss? – John Dvorak – 2014-10-26T02:40:14.840
@JanDvorak If a shot cuts through the ship by entering through a vertex, then this would be a hit because the line segment overlaps the interior of the ship. So in the 4th example, if the range was greater than 5, then this would be a hit. – Sp3000 – 2014-10-26T02:45:48.927
How much are we allowed to play with the arguments? Are we allowed to group them, change the order, or require that they be floats? – FryAmTheEggman – 2014-10-27T18:05:34.187
@FryAmTheEggman You may group or reorder the arguments as necessary. You can use floats, but the program needs to work correctly for small grids (say, up to 20x20) without worrying about precision. – Sp3000 – 2014-10-27T21:38:02.093
I think the examples are missing one important case that make my intended solution fail: when the ship is penetrated through a corner, for example
0 0 -1 3 4 -1 -3 -4 3 4 6
. – nutki – 2014-11-16T13:44:51.197@nutki Indeed, the cases seem to be a bit lacking - I've added two more trickier ones. (I was hoping to see programs which worked in rationals without having to worry about precision, hence the restriction to integer coordinates.) – Sp3000 – 2014-11-17T12:34:44.497
I was working on a solution checking if any of the 3 sides are crossing the cannon line segment. This could be done completely in the integer domain, so no precision loss. But since touching a side is not a hit it will not work with my example. – nutki – 2014-11-17T13:04:05.173