(Too hard? Want to learn some number theory? Consider watching this video by 3blue1brown for some help (or the translated video on Bilibili if you are behind... that thing))

(This is not my original idea. See link to original in a spoiler comment in the 'discourse' section after you solve it.)

Problem statement

You have a large grid in the Cartesian plane. You can draw 4 lines, each passing through two of the lattice points ((x, y) where x and y are integers), and enclosing a square. Note that the vertices of the square need not fall on lattice points; they just need to be on the intersection of two lines. See example diagram below.

Given an area S, determine if there is a group of 4 such lines that enclose a square with area S. And if the answer is yes, provide such a construction.

Details

Since it's all lattice points, we want to go precise. We will only ask you to construct rational areas, and your construction must be exact.

Write a function construct(num, den) that solves the problem for S = num / den.

• num and den will be integers in the range 0 < x < 5000000 (i.e. 5e6)
• If num/den is not possible, return { success: false }
• Otherwise, return { success: true, result: answer } where:
  • A point is an array [x, y] where x and y are integers in JavaScript's 'safe integer' range (from -(253 - 1) inclusive to 253 - 1 inclusive), which represents the point with coordinates (x, y)
  • A line is an array [a, b] where a and b are different points, which represents the line that passes through a and b
  • answer should be an array [l1, l2, l3, l4] of 4 lines that enclose the square with area num/den

Note that performance is important. You will be tested against about 200000 (2e5) inputs, so brute force is probably not going to work too well.

Examples

• 1/2, 5/2, 4/5 are possible
• 1/4, 2/3 are not
• 12/15 is just 4/5, so it's possible

So your code should do something like this:

construct(1, 4)
  => { success: false }

construct(4, 5)
construct(12, 15)
  => (One possible return value)
    {
      success: true,
      result: [
        [[0,0], [1,2]],
        [[1,2], [3,1]],
        [[2,2], [1,0]],
        [[1,1], [3,0]]
      ]
    }

In particular, the construction given for 4/5 looks like: (Hats off to Geogebra)

---

The tests were not easy-to-write at all. I apologize in advance in case a bug stumped you and you weren't able to make your perfectly good solution pass. Please don't hesitate to raise an issue.