Наименьший целочисленный диск

23

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

Ваш ввод будет список точек с целочисленными координатами xи y. Вы можете принять это как список кортежей, список списков или любой другой способ представления коллекции пар. xи yоба будут (возможно, отрицательными) целыми числами. Каждая точка гарантированно уникальна, и будет хотя бы одна точка.

Ваш выход будет диск в виде трех чисел, X, Y, и R. X,, Yи Rвсе целые числа, Xи Yпредставляют центр диска и Rпредставляет его радиус. Расстояние между каждой данной точкой и центром должно быть меньше или равно R, и не должно быть такого диска с меньшим, Rкоторый также удовлетворяет этому условию.

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

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

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

Input   (Possible) Output(s)
(x,y)   (X,Y,R)
-------------------------
(0,0)   (0,0,0)
-------------------------
(0,1)   (0,0,1)
(1,0)   (1,1,1)
-------------------------
(1,4)   (4,4,3)
(3,2)
(4,1)
(4,5)
(5,2)
(7,4)
-------------------------
(-1,0)  (0,0,2)
(2,0)   (1,0,2)
-------------------------
(-1,0)  (1,0,2)
(2,1)   (0,1,2)
-------------------------
(0,0)   (1,0,1)
(1,1)   (0,1,1)

Побеждает несколько байтов.

Павел
источник
Песочница
Павел
Найдена пара опечаток, если вы не возражаете , я указывая на них: «Это сделано несколько трюк я ээ ...»; «... представляет центр диска и R представляет я Т сек радиуса ...»; «... и не должно существовать такой диск ...»
J. Salle
2
Обычно целочисленные вещи делают код-гольф проще.
user202729
@KevinCruijssen Это по стечению обстоятельств. Входы могут быть в любом порядке.
Павел
1
@Pavel Ввод может быть в любом порядке, или мы можем принять вход в любом порядке? Например, входные данные могут быть в любом порядке, и мы должны сначала вручную отсортировать в нашем решении, или мы уже можем взять предварительно отсортированные входные данные?
Кевин Круйссен

Ответы:

6

Желе , 25 24 22 21 20 18 байт

«/r»/Œpµ³_²§½ṀĊ,)Ṃ

Спасибо @EriktheOutgolfer за сообщение об )экономии 1 байта.

Спасибо @Dennis за сохранение 2 байта.

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

объяснение

«/r»/Œpµ³_²§½ṀĊ,)Ṃ      Main link. Arg: points
                        e.g. [[1,4],[3,2],[3,1]]
«/                      Find minimums by coordinate
                        e.g. [1,1]
   »/                   Find maximums by coordinate
                        e.g. [3,4]
  r                     Inclusive ranges by coordinate
                        e.g. [[1,2,3],[1,2,3,4]]
     Œp                 Cartesian product of the x and y ranges
                        e.g. [[1,1],[1,2],[1,3],[1,4],...,[3,4]]
       µ                    Chain, arg: center
                            e.g. [1,3]
        ³                   Get the original points
                            e.g. [[1,4],[3,2],[3,1]]
         _                  Subtract the center from each
                            e.g. [[0,1],[2,-1],[2,-2]]
          ²                 Square each number
                            e.g. [[0,1],[4,1],[4,4]]
           §                Sum each sublist
                            e.g. [1,5,8]
            ½               Square root of each number
                            e.g. [1,2.24,2.83]
             Ṁ              Find the maximum
                            e.g. 2.83
              Ċ             Round up
                            e.g. 3
               ,            Pair with the center point
                            e.g. [3,[1,3]]
                )       Do the above for all points
                        e.g. [[3,[1,1]],[3,[1,2]],[3,[1,3]],...,[3,[3,4]]]
                 Ṃ      Find the lexicographically smallest pair
                        e.g. [3,[1,1]]
PurkkaKoodari
источник
@ Деннис Спасибо! С каких пор векторизация Jelly повторила более короткий список, или я неправильно истолковал удаление ?
PurkkaKoodari
Глубины сопоставляются первыми. Если вы пара и массив пар, пара сопоставляется со всеми парами.
Деннис
8

Brachylog v2, 19 байт

;Az{\-ᵐ~√ᵐ+}ᵐ≤ᵛ√;A≜

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

Эту программу было легко написать - Brachylog почти идеально подходит для такого рода проблем - но трудно для гольфа. Меня не удивит, если где-то здесь сохранится байт, так как некоторые вещи, которые я делал, оказали какое-либо влияние (и содержат инструкции вложенной карты, обычно это признак того, что вы должны использовать member / findall, но я не могу увидеть способ сделать это).

Это функция представления. Ввод осуществляется из левого аргумента функции в формате [[x,y],[x,y],…], вывод из правого аргумента в форме [r,[[x,y]]]. (Если вы хотите попробовать отрицательные числа во входных данных, обратите внимание, что Brachylog использует _для знака минус, а не -. Это сбивает с толку, потому что функция → полная программа-оболочка, с которой поставляется Brachylog, запрошенная с помощью аргумента командной строки Z, будет представлять отрицательные числа в выходной с обычным знаком минус.)

объяснение

;Az{\-ᵐ~√ᵐ+}ᵐ≤ᵛ√;A≜
;A                   Append something
  z                    to every element of the input
   {       }ᵐ        such that for each resulting element:
     -                 Subtracting
    \ ᵐ                  corresponding elements {of the (input, appended) element}
       ~√              and un-squarerooting
         ᵐ               {the result of} each {subtraction}
          +            and summing {the resulting square numbers}
             ≤       {lets us find} a number at least as large as
              ᵛ        every element {of the list of sums}
               √     which can be square-rooted;
                ;A   append the same list as initially to it.
                  ≜  Find the first integer solution to the above, lexicographically.

Это интересно тем, что мы просим Brachylog найти значение определенных свойств (в данном случае радиус диска с центром в точке, Aкоторая соответствует всем входным точкам), но вряд ли предъявляем к нему какие-либо требования (все, что нам нужно, это что радиус это число). Однако Brachylog будет внутренне вычислять рассматриваемый радиус символически, а не пытаться использовать конкретные числа, поэтому, когда достигается окончательный результат , он выполняет две вещи одновременно: во-первых, он гарантирует, что только целые числа используются для координат Aи для радиуса (сделать квадрат радиуса квадратным числом и объяснить, как использовать ≤ᵛ«максимум или больше»); во-вторых, он находит наименьший возможный жизнеспособный радиус (поскольку радиус выводится первым в выходных данных).

Одна вещь, которая вообще не указана в программе, состоит в том, что все точки измеряются относительно одного и того же центра диска; как написано, нет никаких ограничений, что мы не используем разные центры для каждой точки. Однако порядок разрыва связей (который в этом случае устанавливается третьим и который в качестве структурного ограничения будет оцениваться до ограничения значения, подразумеваемого ) хочет Aбыть как можно более коротким (т. Е. Одним элементом, поэтому мы используем тот же самый center каждый раз, Aсначала он пробует нулевую длину, но это, очевидно, не работает, поэтому он пробует следующий список. В результате мы получаем полезное ограничение (что у нас есть только один диск) «бесплатно».

Такое решение обобщает любое количество измерений без изменений в исходном коде; здесь нет никаких предположений, что вещи двумерны. Так что, если вам понадобится наименьшая целочисленная сфера, вы тоже можете это иметь.

оборота ais523
источник
3

Perl 6 , 81 байт

{min [X]([Z]($^p)>>.minmax).map:{$p.map({(@_ Z-$_)>>².sum**.5}).max.ceiling,$_}}

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

Принимает список точек в виде 2-элементных списков ((X1, Y1), (X2, Y2), ...). Возвращает список (R, (X, Y)). Использует тот же подход, что и ответ Jelly от Pietu1998:

[X]([Z]($^p)>>.minmax)  # All possible centers within the bounding box
.map:{ ... }            # mapped to
$p.map({(@_ Z-$_)>>².sum**.5}).max  # maximum distance from any point
.ceiling                # rounded up,
,$_                     # paired with center.
min                     # Find minimum by distance.

minmaxМетод полезен здесь , как это возвращает Range. Декартово произведение диапазонов непосредственно дает все точки с целочисленными координатами.

nwellnhof
источник
2

05AB1E , 26 байт

øεWsàŸ}`âεUIεX-nOt}àîX‚}{н

Порт @ Pietu1998 Желе ответ .

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение:

ø                    # Zip the (implicit) input, swapping the rows and column
                     #  i.e. [[1,4],[3,2],[3,1]] → [[1,3,3],[4,2,1]]
 ε    }              # Map each to:
  W                  #  Push the smallest value (without popping the list)
                     #   i.e. [[1,3,3],[4,2,1]] → [1,1]
   s                 #  Swap so the list is at the top of the stack again
    à                #  Pop the list and push the largest value
                     #   i.e. [[1,3,3],[4,2,1]] → [3,4]
     Ÿ               #  Take the inclusive range of the min and max
                     #   i.e. [[1,2,3],[1,2,3,4]]
`                    # After the map, push both lists separated to the stack
 â                   # And take the cartesian product of the two lists
                     #  i.e. [[1,2,3],[1,2,3,4]]
                     #   → [[1,1],[1,2],[1,3],[1,4],[2,1],[2,2],[2,3],[2,4],[3,1],[3,2],[3,3],[3,4]]
  ε             }    # Map each pair to:
   U                 #  Pop and store the current value in variable `X`
    I                #  Push the input
     ε     }         #  Map each pair in the input to:
      X              #   Push variable `X`
       -             #   Subtract it from the current pair
                     #    i.e. [3,2] - [1,3] → [2,-1]
        n            #   Take the square of each
                     #    i.e. [2,-1] → [4,1]
         O           #   Sum the lists
                     #    i.e. [4,1] → 5
          t          #   Take the square-root of each
                     #    i.e. 5 → 2.23606797749979
            à        #  Pop the converted list, and push its largest value
                     #   i.e. [[3.0,2.23606797749979,2.0],[2.0,2.0,2.23606797749979],...,[2.0,2.0,3.0]]
                     #    → [3.0,2.23606797749979,...,3.0]
             î       #  Round it up
                     #   i.e. [3.0,2.23606797749979,...,3.0] → [3.0,3.0,3.0,4.0,4.0,3.0,3.0,4.0,4.0,3.0,3.0,3.0]
              X     #  Pair it with variable `X`
                     #   i.e. [[3.0,[1,1]],[3.0,[1,2]],...,[3.0,[3,4]]]
                 {   # After the map, sort the list
                  н  # And take the first item (which is output implicitly)
                     #  i.e. [[3.0,[1,1]],[3.0,[1,2]],...,[3.0,[3,4]]] → [3.0,[1,1]]
Кевин Круйссен
источник
2

Matlab, 73 байта

function g(x);[r,~,d]=fminimax(@(a)pdist2(x,a),[0 0]);[round(r) ceil(d)]

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

Позвони с

g([1 4;3 2;4 1;4 5;5 2;7 4])
Jonas
источник
(0,0),(1,1)fminimax(0.5,0.5)(1,1)2/21(0,0)
Вы правы, но вывод fminimax равен [0.500000211699422 0.499999788525202], поэтому он округляется правильно. Так что мне здесь повезло. В настоящее время я думаю, как обойти эту проблему (поскольку это работает только по чистой случайности).
Джонас
2

Pyth , 34 33 байта

hSm+.EeSm@s^R2-Vdk2Qd*Fm}FhM_BSdC

Вывод в виде [R,x,y]

Попробуйте онлайн здесь или проверьте все тестовые примеры сразу здесь .

hSm+.EeSm@s^R2-Vdk2Qd*Fm}FhM_BSdCQ   Implicit: Q=eval(input())
                                     Trailing Q inferred
                                CQ   Transpose (group x and y coordinates separately)
                       m             Map each in the above, as d, using:
                              Sd       Sort d
                            _B         Pair with its own reverse
                          hM           Take the first element of each, yielding [min, max]
                        }F             Generate inclusive range
                     *F              Cartesian product of the above two lists, yielding all coordinates in range
  m                                  Map each coordinate in the above, as d, using:
        m          Q                   Map each coordinate in input, as k, using:
              -Vdk                       Take the difference between x and y coordinates in d and k
           ^R2                           Square each
          s                              Sum
         @        2                      Take the square root
      eS                               Take the largest of the result
    .E                                 Rounded up
   +                d                  Prepend to d
 S                                   Sort the result, first element as most significant
h                                    Take first element

Редактирование: Сохранение байта путем изменения формата вывода, предыдущая версия:

heDm+d.EeSm@s^R2-Vdk2Q*Fm}FhM_BSdC

Sok
источник
2

Wolfram Language (Mathematica) , 66 байт

Вот подход грубой силы. Я рассмотрел гораздо более короткую BoundingRegion[#,"MinDisk"]&функцию, но нет способа принудительно задать целочисленные координаты и радиус.

Minimize[{r,RegionWithin[{x,y}~Disk~r,Point@#]},{x,y,r},Integers]&

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

Келли Лоудер
источник
Ницца. Но как насчет {Round@#[[1]], Ceiling@#[[2]]} &@BoundingRegion[#, "MinDisk"]&?
DavidC
@DavidC, округление центра может сдвинуть его до Sqrt [2] /2=.707, но взятие потолка не обязательно добавит достаточную длину к радиусу, чтобы противостоять этому. Я думаю, что примером такой неудачи могут быть только две точки {{0,0}, {11,11}}
Келли Лоудер
Я понимаю что ты имеешь ввиду!
DavidC
2

Java 10, 283 279 277 257 байт

C->{int M=1<<31,m=M,X=M,Y=M,x=M-1,y=x,t,a,b,r[]={x};for(var c:C){x=(t=c[0])<x?t:x;X=t>X?t:X;y=(t=c[1])<y?t:y;Y=t>Y?t:Y;}for(;y<=Y;y++)for(t=x;t<=X;r=m<r[0]?new int[]{m,t,y}:r,m=M,t++)for(var c:C){a=c[0]-t;b=c[1]-y;a*=a;m=(a=(int)Math.ceil(Math.sqrt(a+=b*=b)))>m?a:m;}return r;}

-20 байт благодаря @nwellnhof кончик «s использования Math.hypot.

Массив результатов находится в порядке [R,X,Y].

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

Объяснение:

C->{                  // Method with 2D int-array as parameter & int-array as return-type
  int M=1<<31,        //  Minimum `M`, starting at -2,147,483,648
      m=M,            //  Temp integer, starting at -2,147,483,648 as well
      X=M,            //  Largest X coordinate, starting at -2,147,483,648 as well
      Y=M,            //  Largest Y coordinate, starting at -2,147,483,648 as well
      x=M-1,          //  Smallest X coordinate, starting at 2,147,483,647
      y=x,            //  Smallest Y coordinate, starting at 2,147,483,647 as well
      t,a,            //  Temp integers, starting uninitialized
      r[]={x};        //  Result-array, starting at one 2,147,483,647
  for(var c:C){       //  Loop over the input-coordinates
    x=(t=c[0])<x?t:x; //   If the X coordinate is smaller than `x`, change it
    X=t>X?t:X;        //   If the X coordinate is larger than `X`, change it
    y=(t=c[1])<y?t:y; //   If the Y coordinate is smaller than `y`, change it
    Y=t>Y?t:Y;}       //   If the Y coordinate is larger than `Y`, change it
 for(;y<=Y;y++)       //  Loop `y` in the range [`y`,`Y`]:
   for(t=x;t<=X       //   Inner loop `t` in the range [`x`,`X`]:
          ;           //     After every iteration:
           r=m<r[0]?  //      If `m` is smaller than the first value:
              new int[]{m,t,y}
                      //       Replace the result with `m,t,y`
             :        //      Else:
              r,      //       Leave `r` unchanged
           m=M,       //      Reset `m` to -2,147,483,648 for the next iteration
           t++)       //      And increase `t` by 1
     for(var c:C)     //    Inner loop over the input-coordinates
       m=(a=(int)Math.ceil(Math.hypot(c[0]-t,c[1]-y)))
                      //     Subtract `t` from the X coordinate;
                      //     subtract `y` from the Y coordinate;
                      //     take the hypot (<- sqrt(x*x+y*y)) of those
                      //     ceil it
                      //     And set `a` to this value
          >m?         //     If `a` is larger than `m`:
           a          //      Set `m` to `a`
          :           //     Else:
           m;         //      Leave `m` unchanged
  return r;}          //  Return the result `r`
Кевин Круйссен
источник
1
Вы можете сохранить как минимум 8 байтов с помощью Math.hypot.
nwellnhof
@nwellnhof Ах, совсем забыли о том Math.hypot, что идеально подходит для этой задачи! -20 байтов прямо там. Спасибо. :)
Кевин Круйссен
1

Javascript, 245 байт

a=>{[b,c,d,e]=a.reduce(([j,k,l,m],[h,i])=>[j>h?j:h,k<h?k:h,l>i?l:i,m<i?m:i],[,,,,]);for(f=c;f<b;f++){for(g=e;g<d;g++){s=a.reduce((o,[p,q])=>o>(r=(p-f)**2+(q-g)**2)?o:r);n=n?n[2]>s?[f,g,s]:n:[f,g,s]}}return [n[0],n[1],Math.ceil(Math.sqrt(n[2]))]}

(Несколько) более читаемая версия:

a=>{
    [b,c,d,e]=a.reduce(([j,k,l,m],[h,i])=>[j>h?j:h,k<h?k:h,l>i?l:i,m<i?m:i],[,,,,]);
    for(f=c;f<b;f++){
        for(g=e;g<d;g++){
            s=a.reduce((o,[p,q])=>o>(r=(p-f)**2+(q-g)**2)?o:r);
            n=n?n[2]>s?[f,g,s]:n:[f,g,s]
        }
    }
    return [n[0],n[1],Math.ceil(Math.sqrt(n[2]))]
}

Просто находит ограничивающую рамку и проверяет каждую координату в этой рамке на предмет того, является ли она лучшей.

Я мог бы сэкономить 8 байтов с приблизительным ответом, заменив:

Math.ceil(Math.sqrt(n[2])) с ~~(n[2]+1-1e-9)

Spitemaster
источник
В гольфе наверняка есть что-то еще, но JS - не моя сильная команда. Тем не менее, вы можете играть в гольф for(f=c;f<b;f++){for(g=e;g<d;g++){s=a.reduce((o,[p,q])=>o>(r=(p-f)**2+(q-g)**2)?o:r);n=n?n[2]>s?[f,g,s]:n:[f,g,s]}}на for(f=c;f<b;f++)for(g=e;g<d;n=n?n[2]>s?[f,g,s]:n:[f,g,s],g++)s=a.reduce((o,[p,q])=>o>(r=(p-f)**2+(q-g)**2)?o:r);. И я почти уверен, что вы можете удалить место в return[.
Кевин Круйссен
1
Вы можете, вероятно, сохранить несколько байтов, используя Math.hypot.
nwellnhof
1

Древесный уголь , 65 байт

≔Eθ§ι¹ζ≔Eθ§ι⁰ηF…·⌊η⌈ηF…·⌊ζ⌈ζ⊞υ⟦ικ⟧≔Eυ⌈EθΣEιX⁻§λξν²ηI§υ⌕η⌊ηI⌈X⌊η·⁵

Попробуйте онлайн! Ссылка на подробную версию кода. Объяснение:

≔Eθ§ι¹ζ

Получить координаты у в z.

≔Eθ§ι⁰η

Получить X-координаты в h.

F…·⌊η⌈ηF…·⌊ζ⌈ζ⊞υ⟦ικ⟧

Цикл по включенным диапазонам от минимумов до максимумов hи zсоздание списка всех потенциальных центров диска.

≔Eυ⌈EθΣEιX⁻§λξν²η

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

I§υ⌕η⌊η

Найдите положение минимального максимального диаметра и напечатайте соответствующий центр диска.

I⌈X⌊η·⁵

Выведите минимальный максимальный диаметр, но округлите его до следующего целого числа.

Нил
источник