В математике циклический четырехугольник - это тот, чьи вершины лежат на одном круге. Другими словами, каждая вершина находится на окружности трех других. Для получения дополнительной информации см. Статью MathWorld .

Примеры

Эти четырехугольники являются циклическими:

Эта трапеция не циклична.

_{(Изображения из Википедии)}

Задача

Учитывая координаты четырех вершин в порядке против часовой стрелки, которые образуют выпуклый четырехугольник, определить, является ли четырехугольник циклическим.

Координаты будут целыми числами (заметьте, однако, что координаты и центр окружности не обязательно являются целыми числами.) Как подразумевается в предыдущем параграфе, никакие три точки не будут коллинеарными и не будут совпадать две.

I / O

Вы можете принять участие в любом разумном формате. В частности, [[x1,x2,x3,x4],[y1,y2,y3,y4]], [[x1,y1],[x2,y2],[x3,y3],[x4,y4]]и комплексные числа все в порядке.

Вывод с использованием любых других непротиворечивых значений для истинного и ложного.

Контрольные примеры

Правда:

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

Ложь:

[0,0], [314,0], [314,100], [0,99]
[31,41],[59,26],[53,58],[0,314]

Wolfram Language (Mathematica) , 23 байта

#∈Circumsphere@{##2}&

Попробуйте онлайн!

Принимает четыре входа: в списках {x1,y1}, {x2,y2}, {x3,y3}, и {x4,y4}. Проверяет, лежит ли первая точка на окружности остальных трех. Также работает для проверки, являются ли точки в конциклическими, если последние из них аффинно независимы (потому что грустно, если вы даете ему вырожденный ввод).$n+1$$\mathbb R^n$$n$Circumsphere

Альтернативно, вот математический подход:

Wolfram Language (Mathematica) , 29 28 25 24 байта

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

Попробуйте онлайн!

Принимает два списка в качестве входных данных: {x1,x2,x3,x4}и {y1,y2,y3,y4}. Возвращает, Indeterminateкогда четыре точки находятся на общем круге, и 1иначе.

Из четырех точек это решение матрицу:$(x_1, y_1), (x_2,y_2), (x_3, y_3), (x_4, y_4)$

$\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}$

Определитель этой матрицы равен 0 тогда и только тогда, когда четыре строки линейно зависимы, а линейная зависимость между строками - это то же самое, что и уравнение окружности, которое выполняется во всех четырех точках.

Самый короткий путь я мог думать , чтобы проверить, определитель 0 является , чтобы поднять его на 0-й степени: 0^0это в Indeterminateто время как все остальное дает 1.

Python 3 , 70 байт

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

Попробуйте онлайн!

Я использую теорему Птолемея .

В четырехугольнике, если сумма произведений его двух пар противоположных сторон равна произведению его диагоналей, то четырехугольник может быть вписан в круг.

b, c, d, eЯвляются комплексными числами.

Perl 6 , 44 байта

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

Попробуйте онлайн!

Принимает вершины как комплексные числа. Используется тот факт, что сумма противоположных углов составляет 180 ° в циклическом четырехугольнике. Порядок операций должен гарантировать, что операции с плавающей точкой дают точный результат для (достаточно малых) целых чисел.

Порт TI-Basic Миши Лаврова, 33 байта

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

Попробуйте онлайн!

JavaScript (ES6)

Тестирование углов, 114 байт

$[x1,y1,x2,y2,x3,y3,x4,y4]$

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

Попробуйте онлайн!

Вычисление определителя, 130 байтов

$[x1,x2,x3,x4]$$[y1,y2,y3,y4]$

Этот эквивалентен второму ответу Миши Лаврова с повернутой матрицей.

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]))

Попробуйте онлайн!

TI-Basic (серия 83), 21 байт

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

Принимает ввод как список четырех комплексных чисел в Ans. Возвращает, 1если четырехугольник циклический и в 0противном случае.

$z_1, z_2, z_3, z_4$

• ΔList(augment(Ans,Ans$z_2-z_1, z_3-z_2, z_4-z_3, z_1-z_4$
• e^(ΔList(ln($\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$
• $\frac{z_3-z_2}{z_2-z_1} \cdot \frac{z_1-z_4}{z_4-z_3}$ $(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}$

Я приложил все усилия, чтобы проверить, является ли числовая ошибка проблемой, и это не кажется, но если у кого-то есть хорошие тестовые случаи для этого, пожалуйста, дайте мне знать.

JavaScript (ES6) (101 байт)

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)

Принимает ввод как [x1,y1,x2,y2,x3,y3,x4,y4], выводит логическое значение.

Попробуйте онлайн!

Желе , 11 байт

²Sṭ;L€€ṖÆḊ¬

Попробуйте онлайн!

Использует детерминантный подход из решения Mathematica Миши Лаврова . Выходы 1 для истины, 0 для ложных.

Как это устроено

²Sṭ;L€€ṖÆḊ¬  Main link (monad). Input: [[x1,x2,x3,x4], [y1,y2,y3,y4]]
²S           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?

Желе , 12 байт

Iµ÷×ƭ/÷SµḞ=A

Попробуйте онлайн!

Использует извилистый перекрестный подход из решения TI-Basic Миши Лаврова . Выходы 1 для истины, 0 для ложных.

Как это устроено

Iµ÷×ƭ/÷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?

Я считаю, что оба пригодны для игры в гольф ...

APL (Dyalog Classic) , 25 байтов

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

Попробуйте онлайн!

Теорема Птолемея, кредит: ответ Кирилл Малышев