Проблема счастливого конца (на самом деле теорема) утверждает, что

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

Эта проблема была названа Полом Эрдосом, когда два математика, которые первыми работали над этой проблемой, Эстер Кляйн и Джордж Секерес, обручились и впоследствии поженились.

Разъяснения:

• Общее положение здесь означает, что никакие три точки не являются коллинеарными.

• Четырехугольник, образованный четырьмя вершинами, всегда будет считаться непересекающимся, независимо от порядка точек. Например, если четыре точки [1 1], [1 2], [2 1], [2 2]предполагаемый четырехугольник является квадратом, а не бантик:

  

• Непересекающийся четырехугольник является выпуклым, если внутренний угол не превышает 180 градусов; или эквивалентно, если обе диагонали лежат внутри четырехугольника.

Соревнование

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

правила

Если существует несколько решений (то есть несколько наборов из 4 точек), вы можете последовательно выбрать вывод одного из них или всех.

Форматы ввода и вывода, как обычно, гибкие (массивы, списки, список списков, строки с разумными разделителями и т. Д.).

Код гольф, побеждает меньше байтов.

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

1. Входные данные:

   [6 8] [1 10] [6 6] [5 9] [8 10]
   

   Возможен только один выход:

   [6 8] [1 10] [6 6] [5 9]
   

2. Входные данные:

   [3 8] [7 5] [6 9] [7 8] [5 1]
   

   Есть пять решений:

   [3 8] [7 5] [6 9] [7 8]
   [3 8] [7 5] [6 9] [5 1]
   [3 8] [7 5] [7 8] [5 1]
   [3 8] [6 9] [7 8] [5 1]
   [7 5] [6 9] [7 8] [5 1]
   

3. Входные данные:

   [4 8] [1 9] [9 9] [10 2] [1 6]
   

   Есть три решения:

   [4 8] [1 9] [10 2] [1 6]
   [4 8] [9 9] [10 2] [1 6]
   [1 9] [9 9] [10 2] [1 6]
   

   Чтобы проиллюстрировать, вот три решения этого случая:

CJam, 37 34 32 байта

{e!Wf<{2*3ew{)f.-~W%.*:-V>},!}=}

Не уверен, достаточно ли :-Vсчастлив, но, как указывает К. Чжан, =}в конце есть. :)

Это печатает только одно решение, потому что удаление дубликатов будет дороже.

Проверьте это здесь.

объяснение

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

Чувство поворота может быть легко получено из точечного произведения. Если вы возьмете три последовательные точки на четырехугольнике и проведете линии от первого ко второму и с первого по третий, а затем спроецируете последние на перпендикуляр первого ... вы получите число, знак которого говорит вам повернуть ли эти три точки влево или вправо. (Я, вероятно, должен добавить диаграмму для этого.) Это «проецирование на перпендикуляр» звучит довольно сложно, но на самом деле это просто означает, что мы переворачиваем один из двух векторов и вычитаем компоненты после умножения, а не добавляем их. Итак, вот код ...

e!       e# Generate all permutations of the five input points.
Wf<      e# Discard the fifth point in each permutations, giving all
         e# possible quadrilaterals.
{        e# Select the first for which this block gives a truthy result...
  2*     e#   Double the list of points, so that it includes each cyclically
         e#   adjacent set of three points.
  3ew    e#   Get all sublists of length 3, i.e. all sets of three consecutive
         e#   points (with two duplicates).
  {      e#   Filter these sets of three points...
    )    e#     Pull off the last point.
    f.-  e#     Subtract it from the other two, giving vectors from it to
         e#     to those.
    ~    e#     Unwrap the array dumping both vectors on the stack.
    W%   e#     Reverse one of them.
    .*   e#     Element-wise multiplication.
    :-   e#     Subtract the second element from the first. This completes
         e#     the projection.
    V>   e#     Check whether it's greater than 0. This is *false* for right-
         e#     turning sets of three points.
  },     e#   If all corners are right-turning, this will result
         e#   in an empty array.
  !      e#   Logical NOT - hence, only quadrilaterals where all corners
         e#   are right-turning give something truthy.
}=

MATLAB, 67 байт

I=input('');for k=~eye(5);if nnz(convhull(I(k,:)))>4;I(k,:),end;end

Входные данные представлены в виде 2D-матрицы, в которой столбцами являются X и Y соответственно:

[6 8; 1 10; 6 6; 5 9; 8 10]
[3 8; 7 5; 6 9; 7 8; 5 1]
[4 8; 1 9; 9 9; 10 2; 1 6]

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

Вот демо , которое немного модифицировано для работы с Octave

объяснение

Это решение принимает все подмножества 4 точек ввода (порядок не имеет значения). Для этого мы создаем единичную матрицу и его отрицания: ~eye(5). Мы перебираем столбцы этой матрицы и k(индекс цикла) представляет собой логический массив, который указывает, какую из 4 точек следует учитывать. Затем мы используем это, чтобы получить эти 4 точки XY из input ( I(k,:)).

Затем мы вычисляем выпуклую оболочку этих 4 точек ( convhull). Выходными данными convhullявляются индексы входных данных, которые соответствуют точкам, составляющим выпуклую оболочку (с первым дублированным индексом, чтобы закрыть корпус).

Для выпуклого четырехугольника все четыре точки будут частью выпуклой оболочки одних и тех же точек ( nnz(convhull(points)) > 4). Если мы обнаружим, что это так, мы отобразим точки, которые были использованы для этой конкретной итерации.

Javascript (ES6), 306 293 283 байта

c=(v,w,x)=>(w[0]-v[0])*(w[1]-x[1])-(w[1]-v[1])*(w[0]-x[0])>0?1:0
i=(v,w,x,y)=>(c(v,w,x)+c(w,x,y)+c(x,y,v)+c(y,v,w))%4==0&&r.push([v,w,x,y])
j=(v,w,x,y)=>{i(v,w,x,y);i(v,w,y,x);i(v,x,w,y)}
k=(v,w,x,y,z)=>{j(v,w,x,y);j(v,w,x,z);j(v,w,y,z);j(v,x,y,z);j(w,x,y,z)}
f=(v)=>(r=[],k(...v),r)

Пояснение :

Функция cвычисляет перекрестное произведение вектора между 3 смежными точками многоугольника и возвращает 1, если оно положительное, и 0 в противном случае (примечание: перекрестное произведение не может быть нулевым, поскольку точки не могут быть коллинеарными).

j=(v,w,x,y)=>{i(v,w,x,y);i(v,w,y,x);i(v,x,w,y)}
k=(v,w,x,y,z)=>{j(v,w,x,y);j(v,w,x,z);j(v,w,y,z);j(v,x,y,z);j(w,x,y,z)}

Функция kи jгенерирует все циклические перестановки (игнорируя изменение порядка) входного массива.

i=(v,w,x,y)=>(c(v,w,x)+c(w,x,y)+c(x,y,v)+c(y,v,w))%4==0&&r.push([v,w,x,y])

Затем вызывается функция 'i' для каждой циклической перестановки, чтобы вычислить сумму функции cдля каждого из 4 триплетов смежных координат. Если все перекрестные произведения имеют один и тот же знак, то все они будут равны 0 или 1 и будут равны 0 (по модулю 4), а многоугольник будет вогнутым и помещается в выходной массив. Если любой триплет имеет другой знак, тогда сумма будет отлична от нуля (по модулю 4), а многоугольник выпуклый.

f=(v)=>(r=[],k(...v),r)

Функция fиспользуется для инициализации выходного массива, а затем вызывает вышеуказанные функции перед возвратом выходных данных.

Тесты :

c=(v,w,x)=>(w[0]-v[0])*(w[1]-x[1])-(w[1]-v[1])*(w[0]-x[0])>0?1:0
i=(v,w,x,y)=>(c(v,w,x)+c(w,x,y)+c(x,y,v)+c(y,v,w))%4==0&&r.push([v,w,x,y])
j=(v,w,x,y)=>{i(v,w,x,y);i(v,w,y,x);i(v,x,w,y)}
k=(v,w,x,y,z)=>{j(v,w,x,y);j(v,w,x,z);j(v,w,y,z);j(v,x,y,z);j(w,x,y,z)}
f=(v)=>(r=[],k(...v),r)

tests = [
  [[6,8],[1,10],[6,6],[5,9],[8,10]],
  [[3,8],[7,5],[6,9],[7,8],[5,1]],
  [[4,8],[1,9],[9,9],[10,2],[1,6]]
];

tests.forEach(
  (test,i)=>{
    console.log( "Test " + (i+1) );
    f(test).forEach(
      (x)=>console.log( "  " + x.map((e)=>"("+e[0]+","+e[1]+")").join(','))
    );
  }
);

Редактировать :

Может также обрабатывать коллинеарные точки, используя оригинальную версию и изменяя первые две строки на:

t=(a,b,c)=>Math.sign((b[0]-a[0])*(b[1]-c[1])-(b[1]-a[1])*(b[0]-c[0]))
p=(a,b,c,d)=>[t(a,b,c),t(b,c,d),t(c,d,a),t(d,a,b)].filter(x=>x).reduce((p,c,i,a)=>p&c==a[0],1)
q=(a,m,n,o)=>[a[0],a[m],a[n],a[o]]
f=(a)=>{r=[];for(i=0;i<5;i++){b=a.slice();b.splice(i,1);r.push(q(b,1,2,3));r.push(q(b,1,3,2));r.push(q(b,2,1,3))}return r.filter((a)=>p(...a))}

Однако, поскольку этот случай специально исключен в вопросе, дополнительные символы не нужны.

Mathematica 105 96 байт

Select[#~Subsets~{4},f@#&]&выбирает из списка (5) баллов те подмножества из 4 баллов, которые удовлетворяют f.

fвыполняется, когда каждая из четырех точек в наборе лежит на RegionBoundaryодной ConvexHullиз четырех точек.

f@p_:=Apply[And,RegionBoundary@ConvexHullMesh@p~RegionMember~#&/@p];
Select[#~Subsets~{4},f@#&]&

Тестовые случаи

1. Давайте рассмотрим 5 выпуклых оболочек подмножеств (каждая из 4 точек) {{6, 8}, {1, 10}, {6, 6}, {5, 9}, {8, 10}} ,

Select[#~Subsets~{4},f@#&[{{6, 8}, {1, 10}, {6, 6}, {5, 9}, {8, 10}}]

{{{6, 8}, {1, 10}, {6, 6}, {5, 9}}}

{{6, 8}, {1, 10}, {6, 6}, {5, 9}} - единственное решение; каждая из четырех точек служит вершиной выпуклой оболочки (из тех же 4 точек).

{{6, 8}, {1, 10}, {6, 6}, {8, 10}} не является решением; выпуклая оболочка имеет только 3 вершины. {6, 8} лежит внутри корпуса.

Остальные подмножества также не являются решениями:

2. {{4, 8}, {1, 9}, {9, 9}, {10, 2}, {1, 6}} имеет три решения.

Select[#~Subsets~{4},f@#&[{{4, 8}, {1, 9}, {9, 9}, {10, 2}, {1, 6}}]

{
{{4, 8}, {1, 9}, {10, 2}, {1, 6}},
{{4, 8}, {9, 9}, {10, 2}, {1, 6 }},
{{1, 9}, {9, 9}, {10, 2}, {1, 6}}
}

3. {{3, 8}, {7, 5}, {6, 9}, {7, 8}, {5, 1}} имеет 5 решений.

Select[#~Subsets~{4},f@#&[{{3, 8}, {7, 5}, {6, 9}, {7, 8}, {5, 1}}]

{
{{3, 8}, {7, 5}, {6, 9}, {7, 8}},
{{3, 8}, {7, 5}, {6, 9}, {5, 1 }},
{{3, 8}, {7, 5}, {7, 8}, {5, 1}},
{{3, 8}, {6, 9}, {7, 8}, {5 , 1}},
{{7, 5}, {6, 9}, {7, 8}, {5, 1}}
}

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

Если какая-либо из точек будет удалена, оставшиеся 4 точки будут вершинами уменьшенной выпуклой оболочки.