[Question]
  [
Fed up with [experimenting on tiny domestic animals](https://en.wikipedia.org/wiki/Schr%C3%B6dinger%27s_cat), Nobel prize-winning Erwin Schrödinger has decided to find the nearest laser and shoot it at things instead. Because... science!
# Description
You will be given two points that the laser passes through and the size of a laser beam, and you must determine where the laser beam *must* have gone, *could* have gone, and *could not* have gone.
The laser beam can be horizontal, vertical, or diagonal. For a size 1 laser beam, they look like this respectively:
```
       #  #
       #   #
#####  #    #
       #     #
       #      #
```
The diagonal laser beam can also be flipped. Size 2 laser beams look like this:
```
       ###  ##
#####  ###  ###
#####  ###   ###
#####  ###    ###
       ###     ##
```
In general, to get a laser beam of size (n), simply take the laser beam of size (n-1) and add a laser beam of size (1) on both sides. As a final example, here are all possible laser beams of size 3, shown on the same "board":
```
###.....#####.....##
####....#####....###
#####...#####...####
.#####..#####..#####
..#####.#####.#####.
...###############..
....#############...
.....###########....
####################
####################
####################
####################
####################
.....###########....
....#############...
...###############..
..#####.#####.#####.
.#####..#####..#####
#####...#####...####
####....#####....###
```
This "board" will always have dimensions of 20x20 (in characters).
# Input
Your program will be given five integers as input. They are, in order, x1, y1, x2, y2, and the size of the laser beam. They must be taken exactly in that order. If you wish, you may take the ordered (x, y) pairs as an array, tuple, list, or other built-in data type that stores two values.
Both of the two points given as input will be within the board, and they are guaranteed to be distinct (i.e. the two points will never be the same). The size of the laser beam is bound to `1 ≤ size < 20`. There will always be at least one possible laser beam that passes through both of the points.
# Output
Your program must output a 20x20 grid of the following characters:
* `#` if every possible laser beam that passes through the two points also passes through this point.
* `.` if there is no laser beam that passes through the two points and this point.
* `?` if some, but not all, of the possible laser beams pass through this point.
* `X` if this is one of the two original input points (this overrides the `#`).
# Test cases
7, 7, 11, 3, 1
```
..............#.....
.............#......
............#.......
...........X........
..........#.........
.........#..........
........#...........
.......X............
......#.............
.....#..............
....#...............
...#................
..#.................
.#..................
#...................
....................
....................
....................
....................
....................
```
18, 18, 1, 1, 2
```
#??.................
?X??................
??#??...............
.??#??..............
..??#??.............
...??#??............
....??#??...........
.....??#??..........
......??#??.........
.......??#??........
........??#??.......
.........??#??......
..........??#??.....
...........??#??....
............??#??...
.............??#??..
..............??#??.
...............??#??
................??X?
.................??#
```
10, 10, 11, 10, 3
```
?????..????????..???
??????.????????.????
????????????????????
????????????????????
.???????????????????
..??????????????????
????????????????????
????????????????????
????????????????????
????????????????????
??????????XX????????
????????????????????
????????????????????
????????????????????
????????????????????
..??????????????????
.???????????????????
????????????????????
????????????????????
??????.????????.????
```
3, 3, 8, 10, 4
```
??????????..........
??????????..........
??????????..........
???X??????..........
???##?????..........
???###????..........
????###????.........
.????###????........
..????###????.......
..?????##?????......
..??????X??????.....
..??????????????....
..???????????????...
..????????????????..
..?????????????????.
..??????????????????
..??????????????????
..????????.?????????
..????????..????????
..????????...???????
```
The test cases were generated with the following Ruby script, located inside a Stack Snippet to conserve vertical space.
```
/*
#!/usr/bin/ruby
$w = $h = 20
class Point
    attr_reader :x, :y
    def initialize x, y
        @x = x
        @y = y
    end
    def inspect
        "(#{@x}, #{@y})"
    end
    def == p
        @x == p.x && @y == p.y
    end
    alias eql? ==
    def hash
        @x * $h + @y
    end
    def valid?
        @x >= 0 && @y >= 0 && @x < $w && @y < $h
    end
end
module Angle
    HORIZONTAL = Point.new(1, 0)
    VERTICAL = Point.new(0, 1)
    DIAG1 = Point.new(1, 1)
    DIAG2 = Point.new(1, -1)
end
def line_points point, angle, size
    points = [point]
    while points[-1].valid?
        points.push Point.new(points[-1].x + angle.x, points[-1].y + angle.y)
    end
    points.pop
    while points[0].valid?
        points.unshift Point.new(points[0].x - angle.x, points[0].y - angle.y)
    end
    points.shift
    if size == 1
        points
    elsif size > 1
        a2 = case angle
            when Angle::HORIZONTAL then Angle::VERTICAL
            when Angle::VERTICAL then Angle::HORIZONTAL
            else Angle::VERTICAL  # HORIZONTAL also works
        end
        (size-1).times do |n|
            np1 = Point.new(point.x + a2.x*(n+1), point.y + a2.y*(n+1))
            np2 = Point.new(point.x - a2.x*(n+1), point.y - a2.y*(n+1))
            points.concat line_points np1, angle, 1 if np1.valid?
            points.concat line_points np2, angle, 1 if np2.valid?
        end
        points
    else
        throw 'something is very wrong'
    end
end
def generate_grid x1, y1, x2, y2, size
    p1 = Point.new(x1, y1)
    p2 = Point.new(x2, y2)
    lasers = []
    points = [Point.new((p1.x + p2.x) / 2, (p1.y + p2.y) / 2)]  # midpoint
    while points.length > 0
        point = points.pop
        new_lasers = Angle.constants
            .map{|angle| line_points point, Angle.const_get(angle), size }
            .select {|laser| laser.include?(p1) && laser.include?(p2) } -
            lasers
        if new_lasers.length > 0
            lasers.concat new_lasers
            points.push Point.new(point.x+1, point.y) if point.x+1 < $w
            points.push Point.new(point.x, point.y+1) if point.y+1 < $h
            points.push Point.new(point.x-1, point.y) if point.x-1 > 0
            points.push Point.new(point.x, point.y-1) if point.y-1 > 0
        end
    end
    grid = Array.new($h) { ?. * $w }
    lasers.each do |laser|
        laser.each do |point|
            grid[point.y][point.x] = ??
        end
    end
    lasers.reduce(:&).each do |point|
        grid[point.y][point.x] = ?#
    end
    grid[p1.y][p1.x] = 'X'
    grid[p2.y][p2.x] = 'X'
    grid
end
testcases = [
    [7, 7, 11, 3, 1],
    [18, 18, 1, 1, 2],
    [10, 10, 11, 10, 3],
    [3, 3, 8, 10, 4]
]
testcases.each do |test|
    puts test * ', '
    puts
    puts generate_grid(*test).map{|line| '    ' + line }
    puts
end
*/
```
# Rules
* Your program must be able to solve each of the test cases in under 30 seconds (on a reasonable machine). This is more of a sanity check, as my test Ruby program solved all of the test cases near-instantaneously.
* This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so the shortest solution wins.
  
[Answer]
# C, ~~291~~ ~~280~~ ~~277~~ 265 bytes
```
x,y,A,C,B,D,a,c,b,d,w,s,t;T(i){return abs(i)<2*w-1;}U(j,k){s+=T(j-k)*T(j)*T(k);t*=T(j-k)*j*k<1;}main(){for(scanf("%i%i%i%i%i",&a,&b,&c,&d,&w);y<20;y+=!x)s=0,t=1,U(A=a-x,C=c-x),U(B=b-y,D=d-y),U(A-B,C-D),U(A+B,C+D),putchar((x=++x%21)?".?#x"[!!s+t+(!A*!B+!C*!D)]:10);}
```
Can be compiled/run using:
*gcc laser.c -o laser && echo "10 10 11 10 3" | ./laser*
Below, the same code with whitespace and explanatory comments:
```
// Integers...
x,y,A,C,B,D,a,c,b,d,w,s,t;
// Is true if i is in range (of something)
T(i){return abs(i)<2*w-1;}
// Tests if lasers (horizontal, vertical, diagonal, etc) can/must exist at this point
// T(j-k) == 0 iff the laser of this direction can exist
// s += 1 iff this laser direction can pass through this point
// t *= 1 iff this laser direction must pass through this point
U(j,k){
    s+=T(j-k)*T(j)*T(k);
    t*=T(j-k)*j*k<1;
}
main(){ 
    // Read input; p0=(a,b), p1=(c,d)
    for(scanf("%i%i%i%i%i",&a,&b,&c,&d,&w); y<20; y+=!x)
        // A, B, C and D represent delta-x and delta-y for each points
        // e.g.: if we're processing (2,3), and p0=(4,5), A=4-2, B=5-3
        // s != 0 iff (x,y) can have some laser through it
        // t == 1 iff all lasers pass through (x,y)
        // (!A*!B+!C*!D) == 1 iff (x,y) is either p0 or p1  
        s=0,t=1,U(A=a-x,C=c-x),U(B=b-y,D=d-y),U(A-B,C-D),U(A+B,C+D),
        putchar((x=++x%21)?".?#x"[!!s+t+(!A*!B+!C*!D)]:10);
}
```
[Answer]
# C, 302 bytes
```
b[400],x,y,s,t,w,d,e,g,k;f(u,v){d=u*x+v*y;e=u*s+v*t;if(e<d)k=e,e=d,d=k;for(k=0;k<400&d+w>e;++k)g=k%20*u+k/20*v,b[k]|=g>e-w&g<d+w|(g<d|g>e)*2;}main(){scanf("%d%d%d%d%d",&x,&y,&s,&t,&w);w=2*w-1;f(1,0);f(0,1);f(1,1);f(1,-1);b[y*20+x]=4;b[t*20+s]=4;for(k=0;k<400;)putchar(".#.?X"[b[k]]),++k%20?0:puts("");}
```
Input is taken from stdin, reading the 5 numbers in the defined order.
Before final size reduction step:
```
#include <stdio.h>
#include <stdlib.h>
int b[400], x, y, s, t, w, d, e, g, k;
void f(int u, int v) {
  d = u * x + v * y;
  e = u * s + v * t;
  if (e < d) k = e, e = d, d = k;
  if (d + w > e) {
    for (k = 0; k < 400; ++k) {
      g = u * (k % 20) + v * (k / 20);
      if (g > e - w && g < d + w) b[k] |= 1;
      if (g < d || g > e) b[k] |= 2;
    }
  }
}
int main() {
  scanf("%d%d%d%d%d", &x, &y, &s, &t, &w);
  w = 2 * w - 1;
  f(1, 0); f(0, 1); f(1, 1); f(1, -1);
  b[y * 20 + x] = 4;
  b[t * 20 + s] = 4;
  for (k = 0; k < 400; ) {
     putchar(".#.?X"[b[k]]);
     ++k % 20 ? 0 : puts("");
  }
}
```
Some explanation of key steps:
* Array `b` holds the state/result. Bit 0 will be set for all pixels that can be reached by a beam. Bit 1 will be set for all pixels that are **not** covered by all beams.
* Function `f` is called for all 4 directions (vertical, horizontal, both diagonals). Its arguments specify the normal vector of the direction.
* In function `f`:
	+ The distance of both input points relative to the direction is calculated (`d` and `e`) as the dot product of the point with the normal vector passed in.
	+ The distances are swapped if necessary so that `d` is always less than or equal to `e`.
	+ If the difference between `d` and `e` is larger than the width of the beam, no beams are possible in this direction.
	+ Otherwise, loop over all pixels. Set bit 0 if the pixel is reachable by any beam, and bit 1 if it is not covered by all beams.
* Mark the two input points with value 4. Since we used bits 0 and 1 to track the state, which results in values 0 to 3, this is the smallest unused value.
* Loop over the pixels in `b`, and convert the values in the range 0 to 4 to their corresponding character while printing them out.
]