Wyzwanie polega na znalezieniu najmniejszego dysku zawierającego określone punkty. Jest to jednak nieco trudniejsze, ponieważ w tym wyzwaniu współrzędne i promień dysku muszą być liczbami całkowitymi.

Wprowadzony zostanie wykaz punktów o współrzędnych całkowitych xi y. Możesz to potraktować jako listę krotek, listę list lub w jakikolwiek inny sposób reprezentujący zbiór par. xi yobie będą (prawdopodobnie ujemnymi) liczbami całkowitymi. Każdy punkt na pewno będzie unikalny i będzie co najmniej jeden punkt.

Jego wynik będzie na dysku w postaci trzech cyfr X, Y, i R. X, Yi Rwszystkie są liczbami całkowitymi Xi Yreprezentują środek dysku oraz Rjego promień. Odległość między każdym danym punktem a środkiem musi być mniejsza lub równa Ri nie może istnieć taki dysk z mniejszym, Rktóry również spełnia ten warunek.

Możliwe, że dla danych wejściowych będzie wiele możliwych rozwiązań, w tym przypadku kod musi wypisać co najmniej jedno z nich.

Możesz użyć dowolnego rodzaju wbudowanych geometrii obsługiwanych przez Twój język, jeśli takie istnieją, a dane wejściowe / wyjściowe mogą odbywać się za pośrednictwem wbudowanych obiektów punktowych / dyskowych zamiast samych liczb.

Przypadki testowe

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)

Wygrywa najmniej bajtów.

Galaretka , 25 24 22 21 20 18 bajtów

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

Dzięki @EriktheOutgolfer za poinformowanie mnie o )zapisaniu 1 bajtu.

Dzięki @Dennis za zapisanie 2 bajtów.

Wypróbuj online!

Wyjaśnienie

«/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]]

Brachylog v2, 19 bajtów

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

Wypróbuj online!

Ten program był łatwy do napisania - Brachylog jest prawie idealny do tego rodzaju problemów - ale trudny do gry w golfa. Nie zdziwiłoby mnie to, gdyby gdzieś tutaj zapisano bajt, ponieważ niewiele rzeczy wydawało się mieć jakikolwiek efekt (i zawiera instrukcje zagnieżdżonej mapy, zwykle znak, że powinieneś używać członka / findall, ale nie mogę znaleźć sposób, aby to zrobić).

To jest przesłanie funkcji. Dane wejściowe są od lewego argumentu do funkcji w formacie [[x,y],[x,y],…], dane wyjściowe od prawego argumentu w formie [r,[[x,y]]]. (Jeśli chcesz wypróbować liczby ujemne na wejściu, zwróć uwagę, że Brachylog używa _znaku minus, a nie -. Jest to mylące, ponieważ funkcja → pełne opakowanie programu, z którym Brachylog jest dostarczany, żądana za pomocą argumentu wiersza poleceń Z, wyświetli liczby ujemne na wyjściu ze zwykłym znakiem minus).

Wyjaśnienie

;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.

Jest to interesujące, ponieważ prosimy Brachylog o znalezienie wartości niektórych właściwości (w tym przypadku promień dysku wyśrodkowany w punkcie, Aktóry pasuje do wszystkich punktów wejściowych), ale z trudem nakładamy na niego jakiekolwiek wymagania (wszystko czego potrzebujemy to że promień jest liczbą). Jednak Brachylog wewnętrznie obliczy dany promień symbolicznie, zamiast próbować użyć konkretnych liczb, więc po osiągnięciu finału ≜osiąga dwie rzeczy naraz: po pierwsze, zapewnia, że ​​tylko liczby całkowite są używane dla współrzędnych Ai dla promienia (zmuszając kwadratowy promień do liczby kwadratowej i wyjaśniając zastosowanie ≤ᵛdo znalezienia „maksimum lub więcej”); po drugie, znajduje najmniejszy możliwy możliwy promień (ponieważ promień jest pierwszy na wyjściu).

Jedną rzeczą, która w ogóle nie jest określona w programie, jest to, że wszystkie punkty są mierzone względem tego samego środka dysku; jak napisano, nie ma żadnych ograniczeń, że nie używamy innego centrum dla każdego punktu. Jednak kolejność rozstrzygania powiązań (która w tym przypadku jest ustawiana przez trzecią ᵐi która jako ograniczenie struktury zostanie ocenione przed założeniem ograniczenia wartości ≜) chce Abyć jak najkrótsza (tj. Pojedynczy element, więc używamy tego samego wyśrodkuj za każdym razem; Anajpierw próbuje zerowej długości, ale to oczywiście nie działa, więc próbuje następnej listy singletonów). W rezultacie uzyskujemy użyteczne ograniczenie (że mamy tylko jeden dysk) „za darmo”.

To rozwiązanie uogólnia się na dowolną liczbę wymiarów , bez zmian w kodzie źródłowym; nie ma tu żadnych założeń, że rzeczy są dwuwymiarowe. Jeśli więc potrzebujesz najmniejszej sfery całkowitej, możesz to również mieć.

Perl 6 , 81 bajtów

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

Wypróbuj online!

Pobiera listę punktów jako listy 2-elementowe ((X1, Y1), (X2, Y2), ...). Zwraca listę (R, (X, Y)). Używa tego samego podejścia, co odpowiedź Galaretki 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.

minmaxMetoda jest przydatna tutaj jak to zwraca Range. Iloczyn kartezjański zakresów daje bezpośrednio wszystkie punkty o współrzędnych całkowitych.

05AB1E , 26 bajtów

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

Port odpowiedzi galaretki @ Pietu1998 .

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

ø                    # 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]]

Matlab, 73 bajty

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

Po prostu znajdź najmniejsze rozwiązanie (zmiennoprzecinkowe) i zaokrąglij do najbliższego punktu i ustaw promień (najgorszy przypadek dla problemu minimaksy). Nie wiem na pewno, czy to daje poprawne rozwiązanie dla wszystkich możliwych przypadków (w ramach precyzji), ale dla przypadków testowych powinno działać (jeśli nie popełniłem błędu pisowni).

Zadzwoń za pomocą

g([1 4;3 2;4 1;4 5;5 2;7 4])

Pyth , 34 33 bajty

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

Dane wyjściowe są w formie [R,x,y]

Spróbuj go online tutaj , lub sprawdzić wszystkie przypadki testowe od razu tutaj .

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

Edycja: Zapisano bajt, zmieniając format wyjściowy, poprzednia wersja:

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

Wolfram Language (Mathematica) , 66 bajtów

Oto podejście brutalnej siły. Rozważyłem znacznie krótszą BoundingRegion[#,"MinDisk"]&funkcję, ale nie ma sposobu na wymuszenie współrzędnych całkowitych i promienia.

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

Wypróbuj online!

Java 10, 283 279 277 257 bajtów

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 bajty dzięki @nwellnhof jest wierzchołek użyciem Math.hypot.

Tablica wyników jest w kolejności [R,X,Y].

Wypróbuj online.

Wyjaśnienie:

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`

JavaScript, 245 bajtów

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

(Nieco) bardziej czytelna wersja:

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

Po prostu znajduje obwiednię i sprawdza każdą współrzędną w tym polu, czy jest najlepsza.

Mógłbym zapisać 8 bajtów z przybliżoną odpowiedzią, zastępując:

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

Rubin , 113 bajtów

->l{a=l.flatten;(z=*a.min..a.max).product(z).map{|x,y|[l.map{|u,v|(((x-u)**2+(y-v)**2)**0.5).ceil}.max,x,y]}.min}

Wypróbuj online!

Węgiel drzewny , 65 bajtów

≔Ｅθ§ι¹ζ≔Ｅθ§ι⁰ηＦ…·⌊η⌈ηＦ…·⌊ζ⌈ζ⊞υ⟦ικ⟧≔Ｅυ⌈ＥθΣＥιＸ⁻§λξν²ηＩ§υ⌕η⌊ηＩ⌈Ｘ⌊η·⁵

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

≔Ｅθ§ι¹ζ

Wprowadź współrzędne Y do z.

≔Ｅθ§ι⁰η

Wprowadź współrzędne X do h.

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

Pętla obejmuje zakresy od minimum do maksimum hi zgeneruje listę wszystkich potencjalnych centrów dyskowych.

≔Ｅυ⌈ＥθΣＥιＸ⁻§λξν²η

Zapętl wszystkie centra dyskowe, następnie zapętl wszystkie oryginalne punkty, a następnie zapisz obie współrzędne, odejmij, kwadrat, suma, weź maksimum i zapisz wynikową listę.

Ｉ§υ⌕η⌊η

Znajdź pozycję minimalnej maksymalnej średnicy i wydrukuj odpowiedni środek tarczy.

Ｉ⌈Ｘ⌊η·⁵

Wydrukuj minimalną maksymalną średnicę, ale zaokrągl ją w górę do następnej liczby całkowitej.