19
\$\begingroup\$

In mathematics, a cyclic quadrilateral is one whose vertices all lie on the same circle. In other words, every vertex is on the circumcircle of the other three. For more information, see the MathWorld article.

Examples

These quadrilaterals are cyclic:

Cyclic quadrilaterals

This trapezoid is not cyclic.

Trapezoid

(Images from Wikipedia)

Objective

Given the coordinates of four vertices in counterclockwise order which form a convex quadrilateral, determine if the quadrilateral is cyclic.

Coordinates will be integers (note, however, that the circumcenter coordinates and circumradius are not necessarily integers.) As implied by the previous paragraph, no three points will be co-linear and no two coincident.

I/O

You may take input using any reasonable format. In particular, [[x1,x2,x3,x4],[y1,y2,y3,y4]], [[x1,y1],[x2,y2],[x3,y3],[x4,y4]] and complex numbers are all fine.

Output using any different consistent values for true and false.

Test cases

True:

[0,0], [314,0], [314,1], [0,1]
[-5,5], [5,-5], [1337,42], [42,1337]
[104, -233], [109, -232], [112, -231], [123, -224]

False:

[0,0], [314,0], [314,100], [0,99]
[31,41],[59,26],[53,58],[0,314]
asked Nov 17, 2018 at 19:52
\$\endgroup\$

8 Answers 8

12
\$\begingroup\$

Wolfram Language (Mathematica), 23 bytes

#∈Circumsphere@{##2}&

Try it online!

Takes four inputs: the lists {x1,y1}, {x2,y2}, {x3,y3}, and {x4,y4}. Checks if the first point lies on the circumcircle of the other three. Also works for checking if \$n+1\$ points in \$\mathbb R^n\$ are concyclic, provided the last \$n\$ of them are affinely independent (because Circumsphere is sad if you give it a degenerate input).

Alternatively, here is a mathematical approach:

Wolfram Language (Mathematica), (削除) 29 (削除ここまで) (削除) 28 (削除ここまで) (削除) 25 (削除ここまで) 24 bytes

Det@{#^2+#2^2,##,1^#}^0&

Try it online!

Takes two lists as input: {x1,x2,x3,x4} and {y1,y2,y3,y4}. Returns Indeterminate when the four points are on a common circle, and 1 otherwise.

From the four points \$(x_1, y_1), (x_2,y_2), (x_3, y_3), (x_4, y_4)\$, this solution constructs the matrix below:

\$\begin{bmatrix}x_1^2 + y_1^2 & x_2^2 + y_2^2 & x_3^2 + y_3^2 & x_4^2 + y_4^2 \\ x_1 & x_2 & x_3 & x_4 \\ y_1 & y_2 & y_3 & y_4 \\ 1 & 1 & 1 & 1 \end{bmatrix}\$

The determinant of this matrix is 0 if and only if the four rows are linearly dependent, and a linear dependency between the rows is the same thing as the equation of a circle that's satisfied at all four points.

The shortest way I could think of to check if the determinant is 0 is to raise it to the 0-th power: 0^0 is Indeterminate while anything else gives 1.

answered Nov 18, 2018 at 3:16
\$\endgroup\$
11
\$\begingroup\$

Python 3, 70 bytes

lambda b,c,d,e,a=abs:a(a(b-d)*a(c-e)-a(b-c)*a(d-e)-a(c-d)*a(b-e))<1e-8

Try it online!

I use the Ptolemy's theorem.

In a quadrilateral, if the sum of the products of its two pairs of opposite sides is equal to the product of its diagonals, then the quadrilateral can be inscribed in a circle.

b, c, d, e are complex numbers.

answered Nov 17, 2018 at 22:59
\$\endgroup\$
8
\$\begingroup\$

Perl 6, 44 bytes

{!im ($^b-$^a)*($^d-$^c)/(($d-$a)*($b-$c)):}

Try it online!

Takes vertices as complex numbers. Uses the fact that the sum of opposite angles is 180° in a cyclic quadrilateral. The order of operations should guarantee that floating-point operations yield an exact result for (small enough) integers.

Port of Misha Lavrov's TI-Basic solution, 33 bytes

{![*](map */*,($_ Z-.rotate)).im}

Try it online!

answered Nov 17, 2018 at 23:43
\$\endgroup\$
4
  • \$\begingroup\$ 42? Is it still accurate? \$\endgroup\$ Commented Nov 18, 2018 at 4:24
  • 1
    \$\begingroup\$ @JoKing No, it's not. \$\endgroup\$ Commented Nov 18, 2018 at 9:44
  • \$\begingroup\$ What does the colon do in this case? It's definitely not a label, and also not a method call. \$\endgroup\$ Commented Nov 18, 2018 at 14:55
  • \$\begingroup\$ @user202729 It is a method call with indirect invocant syntax. \$\endgroup\$ Commented Nov 18, 2018 at 15:44
6
\$\begingroup\$

JavaScript (ES6)

Testing the angles, 114 bytes

Takes input as the array \$[x1,y1,x2,y2,x3,y3,x4,y4]\$. Returns a Boolean value.

a=>(F=i=>(A=Math.atan2)(a[i+3&7]-(y=a[i+1]),a[i+2&7]-a[i])-A(a[i+5&7]-y,a[i+4&7]-a[i]))(0)+F(2)+F(4)+F(6)==Math.PI

Try it online!

Computing a determinant, 130 bytes

Takes input as \$[x1,x2,x3,x4]\$ and \$[y1,y2,y3,y4]\$ in currying syntax. Returns a Boolean value.

This one is equivalent to MishaLavrov's 2nd answer, with a rotated matrix.

x=>y=>!(g=a=>a+a?a.reduce((v,[r],i)=>v+(i&1?-r:r)*g(a.map(r=>r.slice(1)).filter(_=>i--)),0):1)(x.map((X,i)=>[1,Y=y[i],X,X*X+Y*Y]))

Try it online!

answered Nov 17, 2018 at 23:29
\$\endgroup\$
6
\$\begingroup\$

TI-Basic (83 series), 21 bytes

e^(ΔList(ln(ΔList(augment(Ans,Ans
not(imag(Ans(1)Ans(3

Takes input as a list of four complex numbers in Ans. Returns 1 if the quadrilateral is cyclic and 0 otherwise.

This is nwellnhof's cross-ratio computation, in heavy disguise. If we start with values \$z_1, z_2, z_3, z_4\$, then:

  • ΔList(augment(Ans,Ans computes the differences \$z_2-z_1, z_3-z_2, z_4-z_3, z_1-z_4\$ (and a few more redundant terms),
  • e^(ΔList(ln( of that computes the ratios \$\frac{z_3-z_2}{z_2-z_1}, \frac{z_4-z_3}{z_3-z_2}, \frac{z_1-z_4}{z_4-z_3}, \dots\$.
  • We check if the product of the first and third terms, which is \$\frac{z_3-z_2}{z_2-z_1} \cdot \frac{z_1-z_4}{z_4-z_3}\$, has no imaginary part. Note that this is the same as the cross-ratio \$(z_3,z_1;z_2,z_4) = \frac{z_2-z_3}{z_2-z_1} : \frac{z_4-z_3}{z_4-z_1}\$.

I did my best to check if numerical error is a problem, and it doesn't seem to be, but if anyone has good test cases for that, please let me know.

answered Nov 18, 2018 at 17:31
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6) (101 bytes)

p=>(h=(a,b)=>Math.hypot(p[a]-p[b],p[a+1]-p[b+1]))&&((h(2,4)*h(0,6)+h(0,2)*h(4,6)-h(0,4)*h(2,6))<1e-8)

Takes input as [x1,y1,x2,y2,x3,y3,x4,y4], outputs a Boolean.

Checked based on $$ef=ac+bd$$ where \$e,f\$ are the diagonals and \$a,b,c,d\$ are the sides in order.

Try it online!

answered Nov 21, 2018 at 4:42
\$\endgroup\$
2
\$\begingroup\$

Jelly, 11 bytes

2Sṭ;L€€ṖÆḊ¬

Try it online!

Uses the determinant approach from Misha Lavrov's Mathematica solution. Outputs 1 for true, 0 for false.

How it works

2Sṭ;L€€ṖÆḊ¬ Main link (monad). Input: [[x1,x2,x3,x4], [y1,y2,y3,y4]]
2S Square each scalar and add row-wise; [x1*x1+y1*y1, ...]
 ṭ Append to the input
 ;L€€ Add two rows of [1,1,1,1]'s
 Ṗ Remove an extra row
 ÆḊ¬ Is the determinant zero?

Jelly, 12 bytes

×ばつƭ/÷SμḞ=A

Try it online!

Uses the convoluted cross-ratio approach from Misha Lavrov's TI-Basic solution. Outputs 1 for true, 0 for false.

How it works

×ばつƭ/÷SμḞ=A Main link (monad). Input: list of four complex numbers [z1,z2,z3,z4]
I Increments; [z2-z1, z3-z2, z4-z3]
 μ Refocus on above for sum function
 ×ばつƭ/÷S (z2-z1)÷(z3-z2)×ばつ(z4-z3)÷(z4-z1)
 μ Refocus again
 Ḟ=A (real part) == (norm) within error margin
 i.e. imag part is negligible?

I believe both are golfable...

answered Nov 21, 2018 at 7:01
\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Classic), 25 bytes

{0=-/|⍵}(-⌿2 3⍴2/⌽)×ばつ⊃-1↓⊢

Try it online!

Ptolemy's theorem, credit: Кирилл Малышев's answer

answered Nov 22, 2018 at 17:41
\$\endgroup\$

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.