Smallest Integer Disk











up vote
20
down vote

favorite
2












This challenge is about finding the smallest disk that contains some given points. This is made somewhat trickier, however, by the fact that in this challenge, the disk's coordinates and radius must both be integers.



Your input will be a list of points with integer coordinates x and y. You can take this as a list of tuples, a list of lists, or any other way to represent a collection of pairs. x and y will both be (possibly negative) integers. Every point is guaranteed to be unique, and there will be at least one point.



Your output will be a disk in the form of three numbers, X, Y, and R. X, Y, and R are all integers, X and Y represent the disk's center and R represents its radius. The distance between every given point and the center must be less than or equal to R, and there must not exist such a disk with a smaller R that also satisfies this condition.



It is possible that there will be multiple possible solutions for a given input, your code must output at least one of them in this case.



You can use any kinds of geometry builtins your language supports if there are any, and input/output may be through built-in point/disk objects instead of just numbers.



Test Cases



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)


Fewest bytes wins.










share|improve this question
























  • Sandbox
    – Pavel
    Nov 6 at 16:39










  • Found a couple typos, if you don't mind me pointing them out: "This is made somewhat trickier..."; "...represents the disk's center and R represents its radius..."; "...and there must not exist such a disk..."
    – J. Sallé
    Nov 6 at 17:06








  • 2




    Usually making things integer just make code-golf easier.
    – user202729
    Nov 6 at 17:13










  • @KevinCruijssen That's by coincidence. Inputs can be in any order.
    – Pavel
    Nov 6 at 18:04










  • @Pavel The input can be in any order, or we can take the input in any order? As in, the input can be in any order and we should manually sort first in our solution, or can we already take the input pre-sorted?
    – Kevin Cruijssen
    Nov 6 at 18:07

















up vote
20
down vote

favorite
2












This challenge is about finding the smallest disk that contains some given points. This is made somewhat trickier, however, by the fact that in this challenge, the disk's coordinates and radius must both be integers.



Your input will be a list of points with integer coordinates x and y. You can take this as a list of tuples, a list of lists, or any other way to represent a collection of pairs. x and y will both be (possibly negative) integers. Every point is guaranteed to be unique, and there will be at least one point.



Your output will be a disk in the form of three numbers, X, Y, and R. X, Y, and R are all integers, X and Y represent the disk's center and R represents its radius. The distance between every given point and the center must be less than or equal to R, and there must not exist such a disk with a smaller R that also satisfies this condition.



It is possible that there will be multiple possible solutions for a given input, your code must output at least one of them in this case.



You can use any kinds of geometry builtins your language supports if there are any, and input/output may be through built-in point/disk objects instead of just numbers.



Test Cases



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)


Fewest bytes wins.










share|improve this question
























  • Sandbox
    – Pavel
    Nov 6 at 16:39










  • Found a couple typos, if you don't mind me pointing them out: "This is made somewhat trickier..."; "...represents the disk's center and R represents its radius..."; "...and there must not exist such a disk..."
    – J. Sallé
    Nov 6 at 17:06








  • 2




    Usually making things integer just make code-golf easier.
    – user202729
    Nov 6 at 17:13










  • @KevinCruijssen That's by coincidence. Inputs can be in any order.
    – Pavel
    Nov 6 at 18:04










  • @Pavel The input can be in any order, or we can take the input in any order? As in, the input can be in any order and we should manually sort first in our solution, or can we already take the input pre-sorted?
    – Kevin Cruijssen
    Nov 6 at 18:07















up vote
20
down vote

favorite
2









up vote
20
down vote

favorite
2






2





This challenge is about finding the smallest disk that contains some given points. This is made somewhat trickier, however, by the fact that in this challenge, the disk's coordinates and radius must both be integers.



Your input will be a list of points with integer coordinates x and y. You can take this as a list of tuples, a list of lists, or any other way to represent a collection of pairs. x and y will both be (possibly negative) integers. Every point is guaranteed to be unique, and there will be at least one point.



Your output will be a disk in the form of three numbers, X, Y, and R. X, Y, and R are all integers, X and Y represent the disk's center and R represents its radius. The distance between every given point and the center must be less than or equal to R, and there must not exist such a disk with a smaller R that also satisfies this condition.



It is possible that there will be multiple possible solutions for a given input, your code must output at least one of them in this case.



You can use any kinds of geometry builtins your language supports if there are any, and input/output may be through built-in point/disk objects instead of just numbers.



Test Cases



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)


Fewest bytes wins.










share|improve this question















This challenge is about finding the smallest disk that contains some given points. This is made somewhat trickier, however, by the fact that in this challenge, the disk's coordinates and radius must both be integers.



Your input will be a list of points with integer coordinates x and y. You can take this as a list of tuples, a list of lists, or any other way to represent a collection of pairs. x and y will both be (possibly negative) integers. Every point is guaranteed to be unique, and there will be at least one point.



Your output will be a disk in the form of three numbers, X, Y, and R. X, Y, and R are all integers, X and Y represent the disk's center and R represents its radius. The distance between every given point and the center must be less than or equal to R, and there must not exist such a disk with a smaller R that also satisfies this condition.



It is possible that there will be multiple possible solutions for a given input, your code must output at least one of them in this case.



You can use any kinds of geometry builtins your language supports if there are any, and input/output may be through built-in point/disk objects instead of just numbers.



Test Cases



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)


Fewest bytes wins.







code-golf geometry






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 8 at 1:28

























asked Nov 6 at 16:39









Pavel

4,66613187




4,66613187












  • Sandbox
    – Pavel
    Nov 6 at 16:39










  • Found a couple typos, if you don't mind me pointing them out: "This is made somewhat trickier..."; "...represents the disk's center and R represents its radius..."; "...and there must not exist such a disk..."
    – J. Sallé
    Nov 6 at 17:06








  • 2




    Usually making things integer just make code-golf easier.
    – user202729
    Nov 6 at 17:13










  • @KevinCruijssen That's by coincidence. Inputs can be in any order.
    – Pavel
    Nov 6 at 18:04










  • @Pavel The input can be in any order, or we can take the input in any order? As in, the input can be in any order and we should manually sort first in our solution, or can we already take the input pre-sorted?
    – Kevin Cruijssen
    Nov 6 at 18:07




















  • Sandbox
    – Pavel
    Nov 6 at 16:39










  • Found a couple typos, if you don't mind me pointing them out: "This is made somewhat trickier..."; "...represents the disk's center and R represents its radius..."; "...and there must not exist such a disk..."
    – J. Sallé
    Nov 6 at 17:06








  • 2




    Usually making things integer just make code-golf easier.
    – user202729
    Nov 6 at 17:13










  • @KevinCruijssen That's by coincidence. Inputs can be in any order.
    – Pavel
    Nov 6 at 18:04










  • @Pavel The input can be in any order, or we can take the input in any order? As in, the input can be in any order and we should manually sort first in our solution, or can we already take the input pre-sorted?
    – Kevin Cruijssen
    Nov 6 at 18:07


















Sandbox
– Pavel
Nov 6 at 16:39




Sandbox
– Pavel
Nov 6 at 16:39












Found a couple typos, if you don't mind me pointing them out: "This is made somewhat trickier..."; "...represents the disk's center and R represents its radius..."; "...and there must not exist such a disk..."
– J. Sallé
Nov 6 at 17:06






Found a couple typos, if you don't mind me pointing them out: "This is made somewhat trickier..."; "...represents the disk's center and R represents its radius..."; "...and there must not exist such a disk..."
– J. Sallé
Nov 6 at 17:06






2




2




Usually making things integer just make code-golf easier.
– user202729
Nov 6 at 17:13




Usually making things integer just make code-golf easier.
– user202729
Nov 6 at 17:13












@KevinCruijssen That's by coincidence. Inputs can be in any order.
– Pavel
Nov 6 at 18:04




@KevinCruijssen That's by coincidence. Inputs can be in any order.
– Pavel
Nov 6 at 18:04












@Pavel The input can be in any order, or we can take the input in any order? As in, the input can be in any order and we should manually sort first in our solution, or can we already take the input pre-sorted?
– Kevin Cruijssen
Nov 6 at 18:07






@Pavel The input can be in any order, or we can take the input in any order? As in, the input can be in any order and we should manually sort first in our solution, or can we already take the input pre-sorted?
– Kevin Cruijssen
Nov 6 at 18:07












11 Answers
11






active

oldest

votes

















up vote
6
down vote














Jelly, 25 24 22 21 20 18 bytes



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


Thanks to @EriktheOutgolfer for letting me know about ), saving 1 byte.



Thanks to @Dennis for saving 2 bytes.



Try it online!



Explanation



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





share|improve this answer























  • @Dennis Thanks! Since when did Jelly's vectorization repeat the shorter list, or am I misinterpreting the removal of ?
    – Pietu1998
    Nov 6 at 18:33










  • Depths are matched first. If you a pair and an array of pairs, the pair gets matched with all pairs.
    – Dennis
    Nov 6 at 18:34


















up vote
6
down vote














Brachylog v2, 19 bytes



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


Try it online!



This program was easy to write ­– Brachylog's almost perfect for this sort of problem – but hard to golf. It wouldn't surprise me if there was a byte saving somewhere here, as few things I did seemed to have any effect (and it contains nested map instructions, normally a sign that you should be using member/findall, but I can't see a way to do it).



This is a function submission. Input is from the left argument to the function in the format [[x,y],[x,y],…], output from the right argument in the form [r,[[x,y]]]. (If you want to try negative numbers in the input, note that Brachylog uses _ for the minus sign, not -. This is confusing because the function → full program wrapper that Brachylog ships with, requested using the command-line argument Z, will present negative numbers in the output with a regular minus sign.)



Explanation



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


This is interesting in that we're asking Brachylog to find a value of certain properties (in this case, the radius of a disk centred at point A that fits all the input points), but hardly placing any requirements on it (all we require is that the radius is a number). However, Brachylog will internally calculate the radius in question symbolically rather than trying to use concrete numbers, so when the final is reached, it accomplishes two things at once: first, it ensures that only integers are used for the coordinates of A and for the radius (forcing the squared radius to be a square number, and explaining the use of ≤ᵛ to find a "maximum or greater"); second, it finds the smallest possible viable radius (as the radius comes first in the output).



One thing that isn't specified in the program at all is that all the points are measured against the same centre of a disk; as written, there are no constraints that we don't use a different centre for each point. However, the tiebreak order (which in this case is set by the third , and which as a structure constraint will be evaluated before the value constraint implied by ) wants A to be as short as possible (i.e. a single element, so we use the same centre each time; it tries a zero-length A first but that obviously doesn't work, so it tries a singleton list next). As a result, we end up getting a useful constraint (that we only have one disk) "for free".



This solution happens to generalise to any number of dimensions, with no changes to the source code; there are no assumptions here that things are two-dimensional. So if you happen to need the smallest integer sphere, you can have that too.






share|improve this answer






























    up vote
    3
    down vote














    Perl 6, 81 bytes





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


    Try it online!



    Takes a list of points as 2-element lists ((X1, Y1), (X2, Y2), ...). Returns a list (R, (X, Y)). Uses the same approach as Pietu1998's Jelly answer:



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


    The minmax method is useful here as it returns a Range. The Cartesian product of ranges directly yields all points with integer coordinates.






    share|improve this answer






























      up vote
      2
      down vote














      05AB1E, 26 bytes



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


      Port of @Pietu1998's Jelly answer.



      Try it online or verify all test cases.



      Explanation:





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





      share|improve this answer




























        up vote
        2
        down vote













        Matlab, 73 bytes



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


        Simply find the smallest solution (floating point) and round to nearest point and ceil the radius (worst case for the minimax problem). I don't know for sure if that yields the correct solution for all possible cases (within the precision), but for the test cases it should work (if I didn't make a typing error).



        Call it with



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





        share|improve this answer





















        • wouldn't this fail for $(0,0),(1,1)$? the obvious solution returned by fminimax is the midpoint $(0.5,0.5)$, which MATLAB rounds to $(1,1)$. The radius returned is also $sqrt 2 / 2$ which rounds up to $1$, but that then excludes $(0,0)$.
          – Giuseppe
          Nov 7 at 20:45












        • You are correct, but the output of fminimax is [0.500000211699422 0.499999788525202], so it rounds correctly. So I'm lucky here. I'm currently thinking how to sidestep this problem (as it only work by pure luck).
          – Jonas
          Nov 8 at 21:20




















        up vote
        2
        down vote














        Pyth, 34 33 bytes



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


        Output is in the form [R,x,y]



        Try it online here, or verify all the test cases at once here.



        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


        Edit: Saved a byte by rearranging output format, previous version:



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






        share|improve this answer






























          up vote
          2
          down vote














          Wolfram Language (Mathematica), 66 bytes



          Here's a brute force approach. I considered the much shorter BoundingRegion[#,"MinDisk"]& function but there is no way to force integer coordinates & radius.



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


          Try it online!






          share|improve this answer





















          • Nice. But, how about {Round@#[[1]], Ceiling@#[[2]]} &@BoundingRegion[#, "MinDisk"]&?
            – DavidC
            Nov 7 at 19:55












          • @DavidC, the rounding of the center might move it by up to Sqrt[2]/2=.707 but taking the ceiling won't necessarily add enough length to the radius to counteract that. I think an example of that failing would be just the two points {{0,0},{11,11}}
            – Kelly Lowder
            Nov 7 at 20:27










          • I see what you mean!
            – DavidC
            Nov 7 at 23:19


















          up vote
          2
          down vote













          Java 10, 283 279 277 257 bytes





          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 bytes thanks to @nwellnhof's tip of using Math.hypot.



          The result-array is in the order [R,X,Y].



          Try it online.



          Explanation:



          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`





          share|improve this answer



















          • 1




            You can save at least 8 bytes with Math.hypot.
            – nwellnhof
            Nov 7 at 19:44










          • @nwellnhof Ah, completely forgot about Math.hypot, which is perfect for this challenge! -20 bytes right there. Thanks. :)
            – Kevin Cruijssen
            Nov 7 at 20:27


















          up vote
          1
          down vote













          Javascript, 245 bytes



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


          (Somewhat) more readable version:



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


          Just finds the bounding box, and tests each coordinate in that box for whether it's the best.



          I could save 8 bytes with an approximate answer, by replacing:



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






          share|improve this answer





















          • There are for sure more things to golf, but JS isn't my strong suite. Still, you can golf 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]}} to 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);. And I'm pretty sure you can remove the space at return[.
            – Kevin Cruijssen
            Nov 6 at 21:59






          • 1




            You can probably save a few bytes using Math.hypot.
            – nwellnhof
            Nov 7 at 19:48


















          up vote
          1
          down vote














          Ruby, 113 bytes





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


          Try it online!






          share|improve this answer






























            up vote
            1
            down vote














            Charcoal, 65 bytes



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


            Try it online! Link is to verbose version of code. Explanation:



            ≔Eθ§ι¹ζ


            Get the y-coordinates into z.



            ≔Eθ§ι⁰η


            Get the x-coordinates into h.



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


            Loop over the inclusive ranges from the minimums to the maximums of h and z generating the list of all potential disc centres.



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


            Loop over all the disc centres, then loop over all of the original points, then loop over both coordinates, subtract, square, sum, take the maximum, and save the resulting list.



            I§υ⌕η⌊η


            Find the position of the minimal maximum diameter and print the corresponding disc centre.



            I⌈X⌊η·⁵


            Print the minimal maximum diameter, but round it up to the next integer.






            share|improve this answer





















              Your Answer





              StackExchange.ifUsing("editor", function () {
              return StackExchange.using("mathjaxEditing", function () {
              StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
              StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
              });
              });
              }, "mathjax-editing");

              StackExchange.ifUsing("editor", function () {
              StackExchange.using("externalEditor", function () {
              StackExchange.using("snippets", function () {
              StackExchange.snippets.init();
              });
              });
              }, "code-snippets");

              StackExchange.ready(function() {
              var channelOptions = {
              tags: "".split(" "),
              id: "200"
              };
              initTagRenderer("".split(" "), "".split(" "), channelOptions);

              StackExchange.using("externalEditor", function() {
              // Have to fire editor after snippets, if snippets enabled
              if (StackExchange.settings.snippets.snippetsEnabled) {
              StackExchange.using("snippets", function() {
              createEditor();
              });
              }
              else {
              createEditor();
              }
              });

              function createEditor() {
              StackExchange.prepareEditor({
              heartbeatType: 'answer',
              convertImagesToLinks: false,
              noModals: true,
              showLowRepImageUploadWarning: true,
              reputationToPostImages: null,
              bindNavPrevention: true,
              postfix: "",
              imageUploader: {
              brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
              contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
              allowUrls: true
              },
              onDemand: true,
              discardSelector: ".discard-answer"
              ,immediatelyShowMarkdownHelp:true
              });


              }
              });














               

              draft saved


              draft discarded


















              StackExchange.ready(
              function () {
              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f175405%2fsmallest-integer-disk%23new-answer', 'question_page');
              }
              );

              Post as a guest
































              11 Answers
              11






              active

              oldest

              votes








              11 Answers
              11






              active

              oldest

              votes









              active

              oldest

              votes






              active

              oldest

              votes








              up vote
              6
              down vote














              Jelly, 25 24 22 21 20 18 bytes



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


              Thanks to @EriktheOutgolfer for letting me know about ), saving 1 byte.



              Thanks to @Dennis for saving 2 bytes.



              Try it online!



              Explanation



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





              share|improve this answer























              • @Dennis Thanks! Since when did Jelly's vectorization repeat the shorter list, or am I misinterpreting the removal of ?
                – Pietu1998
                Nov 6 at 18:33










              • Depths are matched first. If you a pair and an array of pairs, the pair gets matched with all pairs.
                – Dennis
                Nov 6 at 18:34















              up vote
              6
              down vote














              Jelly, 25 24 22 21 20 18 bytes



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


              Thanks to @EriktheOutgolfer for letting me know about ), saving 1 byte.



              Thanks to @Dennis for saving 2 bytes.



              Try it online!



              Explanation



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





              share|improve this answer























              • @Dennis Thanks! Since when did Jelly's vectorization repeat the shorter list, or am I misinterpreting the removal of ?
                – Pietu1998
                Nov 6 at 18:33










              • Depths are matched first. If you a pair and an array of pairs, the pair gets matched with all pairs.
                – Dennis
                Nov 6 at 18:34













              up vote
              6
              down vote










              up vote
              6
              down vote










              Jelly, 25 24 22 21 20 18 bytes



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


              Thanks to @EriktheOutgolfer for letting me know about ), saving 1 byte.



              Thanks to @Dennis for saving 2 bytes.



              Try it online!



              Explanation



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





              share|improve this answer















              Jelly, 25 24 22 21 20 18 bytes



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


              Thanks to @EriktheOutgolfer for letting me know about ), saving 1 byte.



              Thanks to @Dennis for saving 2 bytes.



              Try it online!



              Explanation



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






              share|improve this answer














              share|improve this answer



              share|improve this answer








              edited Nov 6 at 18:27

























              answered Nov 6 at 17:44









              Pietu1998

              15.4k22780




              15.4k22780












              • @Dennis Thanks! Since when did Jelly's vectorization repeat the shorter list, or am I misinterpreting the removal of ?
                – Pietu1998
                Nov 6 at 18:33










              • Depths are matched first. If you a pair and an array of pairs, the pair gets matched with all pairs.
                – Dennis
                Nov 6 at 18:34


















              • @Dennis Thanks! Since when did Jelly's vectorization repeat the shorter list, or am I misinterpreting the removal of ?
                – Pietu1998
                Nov 6 at 18:33










              • Depths are matched first. If you a pair and an array of pairs, the pair gets matched with all pairs.
                – Dennis
                Nov 6 at 18:34
















              @Dennis Thanks! Since when did Jelly's vectorization repeat the shorter list, or am I misinterpreting the removal of ?
              – Pietu1998
              Nov 6 at 18:33




              @Dennis Thanks! Since when did Jelly's vectorization repeat the shorter list, or am I misinterpreting the removal of ?
              – Pietu1998
              Nov 6 at 18:33












              Depths are matched first. If you a pair and an array of pairs, the pair gets matched with all pairs.
              – Dennis
              Nov 6 at 18:34




              Depths are matched first. If you a pair and an array of pairs, the pair gets matched with all pairs.
              – Dennis
              Nov 6 at 18:34










              up vote
              6
              down vote














              Brachylog v2, 19 bytes



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


              Try it online!



              This program was easy to write ­– Brachylog's almost perfect for this sort of problem – but hard to golf. It wouldn't surprise me if there was a byte saving somewhere here, as few things I did seemed to have any effect (and it contains nested map instructions, normally a sign that you should be using member/findall, but I can't see a way to do it).



              This is a function submission. Input is from the left argument to the function in the format [[x,y],[x,y],…], output from the right argument in the form [r,[[x,y]]]. (If you want to try negative numbers in the input, note that Brachylog uses _ for the minus sign, not -. This is confusing because the function → full program wrapper that Brachylog ships with, requested using the command-line argument Z, will present negative numbers in the output with a regular minus sign.)



              Explanation



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


              This is interesting in that we're asking Brachylog to find a value of certain properties (in this case, the radius of a disk centred at point A that fits all the input points), but hardly placing any requirements on it (all we require is that the radius is a number). However, Brachylog will internally calculate the radius in question symbolically rather than trying to use concrete numbers, so when the final is reached, it accomplishes two things at once: first, it ensures that only integers are used for the coordinates of A and for the radius (forcing the squared radius to be a square number, and explaining the use of ≤ᵛ to find a "maximum or greater"); second, it finds the smallest possible viable radius (as the radius comes first in the output).



              One thing that isn't specified in the program at all is that all the points are measured against the same centre of a disk; as written, there are no constraints that we don't use a different centre for each point. However, the tiebreak order (which in this case is set by the third , and which as a structure constraint will be evaluated before the value constraint implied by ) wants A to be as short as possible (i.e. a single element, so we use the same centre each time; it tries a zero-length A first but that obviously doesn't work, so it tries a singleton list next). As a result, we end up getting a useful constraint (that we only have one disk) "for free".



              This solution happens to generalise to any number of dimensions, with no changes to the source code; there are no assumptions here that things are two-dimensional. So if you happen to need the smallest integer sphere, you can have that too.






              share|improve this answer



























                up vote
                6
                down vote














                Brachylog v2, 19 bytes



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


                Try it online!



                This program was easy to write ­– Brachylog's almost perfect for this sort of problem – but hard to golf. It wouldn't surprise me if there was a byte saving somewhere here, as few things I did seemed to have any effect (and it contains nested map instructions, normally a sign that you should be using member/findall, but I can't see a way to do it).



                This is a function submission. Input is from the left argument to the function in the format [[x,y],[x,y],…], output from the right argument in the form [r,[[x,y]]]. (If you want to try negative numbers in the input, note that Brachylog uses _ for the minus sign, not -. This is confusing because the function → full program wrapper that Brachylog ships with, requested using the command-line argument Z, will present negative numbers in the output with a regular minus sign.)



                Explanation



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


                This is interesting in that we're asking Brachylog to find a value of certain properties (in this case, the radius of a disk centred at point A that fits all the input points), but hardly placing any requirements on it (all we require is that the radius is a number). However, Brachylog will internally calculate the radius in question symbolically rather than trying to use concrete numbers, so when the final is reached, it accomplishes two things at once: first, it ensures that only integers are used for the coordinates of A and for the radius (forcing the squared radius to be a square number, and explaining the use of ≤ᵛ to find a "maximum or greater"); second, it finds the smallest possible viable radius (as the radius comes first in the output).



                One thing that isn't specified in the program at all is that all the points are measured against the same centre of a disk; as written, there are no constraints that we don't use a different centre for each point. However, the tiebreak order (which in this case is set by the third , and which as a structure constraint will be evaluated before the value constraint implied by ) wants A to be as short as possible (i.e. a single element, so we use the same centre each time; it tries a zero-length A first but that obviously doesn't work, so it tries a singleton list next). As a result, we end up getting a useful constraint (that we only have one disk) "for free".



                This solution happens to generalise to any number of dimensions, with no changes to the source code; there are no assumptions here that things are two-dimensional. So if you happen to need the smallest integer sphere, you can have that too.






                share|improve this answer

























                  up vote
                  6
                  down vote










                  up vote
                  6
                  down vote










                  Brachylog v2, 19 bytes



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


                  Try it online!



                  This program was easy to write ­– Brachylog's almost perfect for this sort of problem – but hard to golf. It wouldn't surprise me if there was a byte saving somewhere here, as few things I did seemed to have any effect (and it contains nested map instructions, normally a sign that you should be using member/findall, but I can't see a way to do it).



                  This is a function submission. Input is from the left argument to the function in the format [[x,y],[x,y],…], output from the right argument in the form [r,[[x,y]]]. (If you want to try negative numbers in the input, note that Brachylog uses _ for the minus sign, not -. This is confusing because the function → full program wrapper that Brachylog ships with, requested using the command-line argument Z, will present negative numbers in the output with a regular minus sign.)



                  Explanation



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


                  This is interesting in that we're asking Brachylog to find a value of certain properties (in this case, the radius of a disk centred at point A that fits all the input points), but hardly placing any requirements on it (all we require is that the radius is a number). However, Brachylog will internally calculate the radius in question symbolically rather than trying to use concrete numbers, so when the final is reached, it accomplishes two things at once: first, it ensures that only integers are used for the coordinates of A and for the radius (forcing the squared radius to be a square number, and explaining the use of ≤ᵛ to find a "maximum or greater"); second, it finds the smallest possible viable radius (as the radius comes first in the output).



                  One thing that isn't specified in the program at all is that all the points are measured against the same centre of a disk; as written, there are no constraints that we don't use a different centre for each point. However, the tiebreak order (which in this case is set by the third , and which as a structure constraint will be evaluated before the value constraint implied by ) wants A to be as short as possible (i.e. a single element, so we use the same centre each time; it tries a zero-length A first but that obviously doesn't work, so it tries a singleton list next). As a result, we end up getting a useful constraint (that we only have one disk) "for free".



                  This solution happens to generalise to any number of dimensions, with no changes to the source code; there are no assumptions here that things are two-dimensional. So if you happen to need the smallest integer sphere, you can have that too.






                  share|improve this answer















                  Brachylog v2, 19 bytes



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


                  Try it online!



                  This program was easy to write ­– Brachylog's almost perfect for this sort of problem – but hard to golf. It wouldn't surprise me if there was a byte saving somewhere here, as few things I did seemed to have any effect (and it contains nested map instructions, normally a sign that you should be using member/findall, but I can't see a way to do it).



                  This is a function submission. Input is from the left argument to the function in the format [[x,y],[x,y],…], output from the right argument in the form [r,[[x,y]]]. (If you want to try negative numbers in the input, note that Brachylog uses _ for the minus sign, not -. This is confusing because the function → full program wrapper that Brachylog ships with, requested using the command-line argument Z, will present negative numbers in the output with a regular minus sign.)



                  Explanation



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


                  This is interesting in that we're asking Brachylog to find a value of certain properties (in this case, the radius of a disk centred at point A that fits all the input points), but hardly placing any requirements on it (all we require is that the radius is a number). However, Brachylog will internally calculate the radius in question symbolically rather than trying to use concrete numbers, so when the final is reached, it accomplishes two things at once: first, it ensures that only integers are used for the coordinates of A and for the radius (forcing the squared radius to be a square number, and explaining the use of ≤ᵛ to find a "maximum or greater"); second, it finds the smallest possible viable radius (as the radius comes first in the output).



                  One thing that isn't specified in the program at all is that all the points are measured against the same centre of a disk; as written, there are no constraints that we don't use a different centre for each point. However, the tiebreak order (which in this case is set by the third , and which as a structure constraint will be evaluated before the value constraint implied by ) wants A to be as short as possible (i.e. a single element, so we use the same centre each time; it tries a zero-length A first but that obviously doesn't work, so it tries a singleton list next). As a result, we end up getting a useful constraint (that we only have one disk) "for free".



                  This solution happens to generalise to any number of dimensions, with no changes to the source code; there are no assumptions here that things are two-dimensional. So if you happen to need the smallest integer sphere, you can have that too.







                  share|improve this answer














                  share|improve this answer



                  share|improve this answer








                  edited Nov 8 at 0:54


























                  community wiki





                  2 revs
                  ais523























                      up vote
                      3
                      down vote














                      Perl 6, 81 bytes





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


                      Try it online!



                      Takes a list of points as 2-element lists ((X1, Y1), (X2, Y2), ...). Returns a list (R, (X, Y)). Uses the same approach as Pietu1998's Jelly answer:



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


                      The minmax method is useful here as it returns a Range. The Cartesian product of ranges directly yields all points with integer coordinates.






                      share|improve this answer



























                        up vote
                        3
                        down vote














                        Perl 6, 81 bytes





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


                        Try it online!



                        Takes a list of points as 2-element lists ((X1, Y1), (X2, Y2), ...). Returns a list (R, (X, Y)). Uses the same approach as Pietu1998's Jelly answer:



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


                        The minmax method is useful here as it returns a Range. The Cartesian product of ranges directly yields all points with integer coordinates.






                        share|improve this answer

























                          up vote
                          3
                          down vote










                          up vote
                          3
                          down vote










                          Perl 6, 81 bytes





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


                          Try it online!



                          Takes a list of points as 2-element lists ((X1, Y1), (X2, Y2), ...). Returns a list (R, (X, Y)). Uses the same approach as Pietu1998's Jelly answer:



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


                          The minmax method is useful here as it returns a Range. The Cartesian product of ranges directly yields all points with integer coordinates.






                          share|improve this answer















                          Perl 6, 81 bytes





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


                          Try it online!



                          Takes a list of points as 2-element lists ((X1, Y1), (X2, Y2), ...). Returns a list (R, (X, Y)). Uses the same approach as Pietu1998's Jelly answer:



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


                          The minmax method is useful here as it returns a Range. The Cartesian product of ranges directly yields all points with integer coordinates.







                          share|improve this answer














                          share|improve this answer



                          share|improve this answer








                          edited Nov 7 at 10:24

























                          answered Nov 6 at 23:23









                          nwellnhof

                          5,608921




                          5,608921






















                              up vote
                              2
                              down vote














                              05AB1E, 26 bytes



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


                              Port of @Pietu1998's Jelly answer.



                              Try it online or verify all test cases.



                              Explanation:





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





                              share|improve this answer

























                                up vote
                                2
                                down vote














                                05AB1E, 26 bytes



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


                                Port of @Pietu1998's Jelly answer.



                                Try it online or verify all test cases.



                                Explanation:





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





                                share|improve this answer























                                  up vote
                                  2
                                  down vote










                                  up vote
                                  2
                                  down vote










                                  05AB1E, 26 bytes



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


                                  Port of @Pietu1998's Jelly answer.



                                  Try it online or verify all test cases.



                                  Explanation:





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





                                  share|improve this answer













                                  05AB1E, 26 bytes



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


                                  Port of @Pietu1998's Jelly answer.



                                  Try it online or verify all test cases.



                                  Explanation:





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






                                  share|improve this answer












                                  share|improve this answer



                                  share|improve this answer










                                  answered Nov 6 at 19:16









                                  Kevin Cruijssen

                                  33.2k554177




                                  33.2k554177






















                                      up vote
                                      2
                                      down vote













                                      Matlab, 73 bytes



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


                                      Simply find the smallest solution (floating point) and round to nearest point and ceil the radius (worst case for the minimax problem). I don't know for sure if that yields the correct solution for all possible cases (within the precision), but for the test cases it should work (if I didn't make a typing error).



                                      Call it with



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





                                      share|improve this answer





















                                      • wouldn't this fail for $(0,0),(1,1)$? the obvious solution returned by fminimax is the midpoint $(0.5,0.5)$, which MATLAB rounds to $(1,1)$. The radius returned is also $sqrt 2 / 2$ which rounds up to $1$, but that then excludes $(0,0)$.
                                        – Giuseppe
                                        Nov 7 at 20:45












                                      • You are correct, but the output of fminimax is [0.500000211699422 0.499999788525202], so it rounds correctly. So I'm lucky here. I'm currently thinking how to sidestep this problem (as it only work by pure luck).
                                        – Jonas
                                        Nov 8 at 21:20

















                                      up vote
                                      2
                                      down vote













                                      Matlab, 73 bytes



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


                                      Simply find the smallest solution (floating point) and round to nearest point and ceil the radius (worst case for the minimax problem). I don't know for sure if that yields the correct solution for all possible cases (within the precision), but for the test cases it should work (if I didn't make a typing error).



                                      Call it with



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





                                      share|improve this answer





















                                      • wouldn't this fail for $(0,0),(1,1)$? the obvious solution returned by fminimax is the midpoint $(0.5,0.5)$, which MATLAB rounds to $(1,1)$. The radius returned is also $sqrt 2 / 2$ which rounds up to $1$, but that then excludes $(0,0)$.
                                        – Giuseppe
                                        Nov 7 at 20:45












                                      • You are correct, but the output of fminimax is [0.500000211699422 0.499999788525202], so it rounds correctly. So I'm lucky here. I'm currently thinking how to sidestep this problem (as it only work by pure luck).
                                        – Jonas
                                        Nov 8 at 21:20















                                      up vote
                                      2
                                      down vote










                                      up vote
                                      2
                                      down vote









                                      Matlab, 73 bytes



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


                                      Simply find the smallest solution (floating point) and round to nearest point and ceil the radius (worst case for the minimax problem). I don't know for sure if that yields the correct solution for all possible cases (within the precision), but for the test cases it should work (if I didn't make a typing error).



                                      Call it with



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





                                      share|improve this answer












                                      Matlab, 73 bytes



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


                                      Simply find the smallest solution (floating point) and round to nearest point and ceil the radius (worst case for the minimax problem). I don't know for sure if that yields the correct solution for all possible cases (within the precision), but for the test cases it should work (if I didn't make a typing error).



                                      Call it with



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






                                      share|improve this answer












                                      share|improve this answer



                                      share|improve this answer










                                      answered Nov 7 at 0:28









                                      Jonas

                                      1774




                                      1774












                                      • wouldn't this fail for $(0,0),(1,1)$? the obvious solution returned by fminimax is the midpoint $(0.5,0.5)$, which MATLAB rounds to $(1,1)$. The radius returned is also $sqrt 2 / 2$ which rounds up to $1$, but that then excludes $(0,0)$.
                                        – Giuseppe
                                        Nov 7 at 20:45












                                      • You are correct, but the output of fminimax is [0.500000211699422 0.499999788525202], so it rounds correctly. So I'm lucky here. I'm currently thinking how to sidestep this problem (as it only work by pure luck).
                                        – Jonas
                                        Nov 8 at 21:20




















                                      • wouldn't this fail for $(0,0),(1,1)$? the obvious solution returned by fminimax is the midpoint $(0.5,0.5)$, which MATLAB rounds to $(1,1)$. The radius returned is also $sqrt 2 / 2$ which rounds up to $1$, but that then excludes $(0,0)$.
                                        – Giuseppe
                                        Nov 7 at 20:45












                                      • You are correct, but the output of fminimax is [0.500000211699422 0.499999788525202], so it rounds correctly. So I'm lucky here. I'm currently thinking how to sidestep this problem (as it only work by pure luck).
                                        – Jonas
                                        Nov 8 at 21:20


















                                      wouldn't this fail for $(0,0),(1,1)$? the obvious solution returned by fminimax is the midpoint $(0.5,0.5)$, which MATLAB rounds to $(1,1)$. The radius returned is also $sqrt 2 / 2$ which rounds up to $1$, but that then excludes $(0,0)$.
                                      – Giuseppe
                                      Nov 7 at 20:45






                                      wouldn't this fail for $(0,0),(1,1)$? the obvious solution returned by fminimax is the midpoint $(0.5,0.5)$, which MATLAB rounds to $(1,1)$. The radius returned is also $sqrt 2 / 2$ which rounds up to $1$, but that then excludes $(0,0)$.
                                      – Giuseppe
                                      Nov 7 at 20:45














                                      You are correct, but the output of fminimax is [0.500000211699422 0.499999788525202], so it rounds correctly. So I'm lucky here. I'm currently thinking how to sidestep this problem (as it only work by pure luck).
                                      – Jonas
                                      Nov 8 at 21:20






                                      You are correct, but the output of fminimax is [0.500000211699422 0.499999788525202], so it rounds correctly. So I'm lucky here. I'm currently thinking how to sidestep this problem (as it only work by pure luck).
                                      – Jonas
                                      Nov 8 at 21:20












                                      up vote
                                      2
                                      down vote














                                      Pyth, 34 33 bytes



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


                                      Output is in the form [R,x,y]



                                      Try it online here, or verify all the test cases at once here.



                                      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


                                      Edit: Saved a byte by rearranging output format, previous version:



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






                                      share|improve this answer



























                                        up vote
                                        2
                                        down vote














                                        Pyth, 34 33 bytes



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


                                        Output is in the form [R,x,y]



                                        Try it online here, or verify all the test cases at once here.



                                        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


                                        Edit: Saved a byte by rearranging output format, previous version:



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






                                        share|improve this answer

























                                          up vote
                                          2
                                          down vote










                                          up vote
                                          2
                                          down vote










                                          Pyth, 34 33 bytes



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


                                          Output is in the form [R,x,y]



                                          Try it online here, or verify all the test cases at once here.



                                          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


                                          Edit: Saved a byte by rearranging output format, previous version:



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






                                          share|improve this answer















                                          Pyth, 34 33 bytes



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


                                          Output is in the form [R,x,y]



                                          Try it online here, or verify all the test cases at once here.



                                          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


                                          Edit: Saved a byte by rearranging output format, previous version:



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







                                          share|improve this answer














                                          share|improve this answer



                                          share|improve this answer








                                          edited Nov 7 at 11:50

























                                          answered Nov 7 at 11:41









                                          Sok

                                          3,309722




                                          3,309722






















                                              up vote
                                              2
                                              down vote














                                              Wolfram Language (Mathematica), 66 bytes



                                              Here's a brute force approach. I considered the much shorter BoundingRegion[#,"MinDisk"]& function but there is no way to force integer coordinates & radius.



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


                                              Try it online!






                                              share|improve this answer





















                                              • Nice. But, how about {Round@#[[1]], Ceiling@#[[2]]} &@BoundingRegion[#, "MinDisk"]&?
                                                – DavidC
                                                Nov 7 at 19:55












                                              • @DavidC, the rounding of the center might move it by up to Sqrt[2]/2=.707 but taking the ceiling won't necessarily add enough length to the radius to counteract that. I think an example of that failing would be just the two points {{0,0},{11,11}}
                                                – Kelly Lowder
                                                Nov 7 at 20:27










                                              • I see what you mean!
                                                – DavidC
                                                Nov 7 at 23:19















                                              up vote
                                              2
                                              down vote














                                              Wolfram Language (Mathematica), 66 bytes



                                              Here's a brute force approach. I considered the much shorter BoundingRegion[#,"MinDisk"]& function but there is no way to force integer coordinates & radius.



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


                                              Try it online!






                                              share|improve this answer





















                                              • Nice. But, how about {Round@#[[1]], Ceiling@#[[2]]} &@BoundingRegion[#, "MinDisk"]&?
                                                – DavidC
                                                Nov 7 at 19:55












                                              • @DavidC, the rounding of the center might move it by up to Sqrt[2]/2=.707 but taking the ceiling won't necessarily add enough length to the radius to counteract that. I think an example of that failing would be just the two points {{0,0},{11,11}}
                                                – Kelly Lowder
                                                Nov 7 at 20:27










                                              • I see what you mean!
                                                – DavidC
                                                Nov 7 at 23:19













                                              up vote
                                              2
                                              down vote










                                              up vote
                                              2
                                              down vote










                                              Wolfram Language (Mathematica), 66 bytes



                                              Here's a brute force approach. I considered the much shorter BoundingRegion[#,"MinDisk"]& function but there is no way to force integer coordinates & radius.



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


                                              Try it online!






                                              share|improve this answer













                                              Wolfram Language (Mathematica), 66 bytes



                                              Here's a brute force approach. I considered the much shorter BoundingRegion[#,"MinDisk"]& function but there is no way to force integer coordinates & radius.



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


                                              Try it online!







                                              share|improve this answer












                                              share|improve this answer



                                              share|improve this answer










                                              answered Nov 7 at 17:34









                                              Kelly Lowder

                                              2,918316




                                              2,918316












                                              • Nice. But, how about {Round@#[[1]], Ceiling@#[[2]]} &@BoundingRegion[#, "MinDisk"]&?
                                                – DavidC
                                                Nov 7 at 19:55












                                              • @DavidC, the rounding of the center might move it by up to Sqrt[2]/2=.707 but taking the ceiling won't necessarily add enough length to the radius to counteract that. I think an example of that failing would be just the two points {{0,0},{11,11}}
                                                – Kelly Lowder
                                                Nov 7 at 20:27










                                              • I see what you mean!
                                                – DavidC
                                                Nov 7 at 23:19


















                                              • Nice. But, how about {Round@#[[1]], Ceiling@#[[2]]} &@BoundingRegion[#, "MinDisk"]&?
                                                – DavidC
                                                Nov 7 at 19:55












                                              • @DavidC, the rounding of the center might move it by up to Sqrt[2]/2=.707 but taking the ceiling won't necessarily add enough length to the radius to counteract that. I think an example of that failing would be just the two points {{0,0},{11,11}}
                                                – Kelly Lowder
                                                Nov 7 at 20:27










                                              • I see what you mean!
                                                – DavidC
                                                Nov 7 at 23:19
















                                              Nice. But, how about {Round@#[[1]], Ceiling@#[[2]]} &@BoundingRegion[#, "MinDisk"]&?
                                              – DavidC
                                              Nov 7 at 19:55






                                              Nice. But, how about {Round@#[[1]], Ceiling@#[[2]]} &@BoundingRegion[#, "MinDisk"]&?
                                              – DavidC
                                              Nov 7 at 19:55














                                              @DavidC, the rounding of the center might move it by up to Sqrt[2]/2=.707 but taking the ceiling won't necessarily add enough length to the radius to counteract that. I think an example of that failing would be just the two points {{0,0},{11,11}}
                                              – Kelly Lowder
                                              Nov 7 at 20:27




                                              @DavidC, the rounding of the center might move it by up to Sqrt[2]/2=.707 but taking the ceiling won't necessarily add enough length to the radius to counteract that. I think an example of that failing would be just the two points {{0,0},{11,11}}
                                              – Kelly Lowder
                                              Nov 7 at 20:27












                                              I see what you mean!
                                              – DavidC
                                              Nov 7 at 23:19




                                              I see what you mean!
                                              – DavidC
                                              Nov 7 at 23:19










                                              up vote
                                              2
                                              down vote













                                              Java 10, 283 279 277 257 bytes





                                              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 bytes thanks to @nwellnhof's tip of using Math.hypot.



                                              The result-array is in the order [R,X,Y].



                                              Try it online.



                                              Explanation:



                                              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`





                                              share|improve this answer



















                                              • 1




                                                You can save at least 8 bytes with Math.hypot.
                                                – nwellnhof
                                                Nov 7 at 19:44










                                              • @nwellnhof Ah, completely forgot about Math.hypot, which is perfect for this challenge! -20 bytes right there. Thanks. :)
                                                – Kevin Cruijssen
                                                Nov 7 at 20:27















                                              up vote
                                              2
                                              down vote













                                              Java 10, 283 279 277 257 bytes





                                              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 bytes thanks to @nwellnhof's tip of using Math.hypot.



                                              The result-array is in the order [R,X,Y].



                                              Try it online.



                                              Explanation:



                                              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`





                                              share|improve this answer



















                                              • 1




                                                You can save at least 8 bytes with Math.hypot.
                                                – nwellnhof
                                                Nov 7 at 19:44










                                              • @nwellnhof Ah, completely forgot about Math.hypot, which is perfect for this challenge! -20 bytes right there. Thanks. :)
                                                – Kevin Cruijssen
                                                Nov 7 at 20:27













                                              up vote
                                              2
                                              down vote










                                              up vote
                                              2
                                              down vote









                                              Java 10, 283 279 277 257 bytes





                                              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 bytes thanks to @nwellnhof's tip of using Math.hypot.



                                              The result-array is in the order [R,X,Y].



                                              Try it online.



                                              Explanation:



                                              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`





                                              share|improve this answer














                                              Java 10, 283 279 277 257 bytes





                                              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 bytes thanks to @nwellnhof's tip of using Math.hypot.



                                              The result-array is in the order [R,X,Y].



                                              Try it online.



                                              Explanation:



                                              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`






                                              share|improve this answer














                                              share|improve this answer



                                              share|improve this answer








                                              edited Nov 7 at 20:26

























                                              answered Nov 7 at 10:49









                                              Kevin Cruijssen

                                              33.2k554177




                                              33.2k554177








                                              • 1




                                                You can save at least 8 bytes with Math.hypot.
                                                – nwellnhof
                                                Nov 7 at 19:44










                                              • @nwellnhof Ah, completely forgot about Math.hypot, which is perfect for this challenge! -20 bytes right there. Thanks. :)
                                                – Kevin Cruijssen
                                                Nov 7 at 20:27














                                              • 1




                                                You can save at least 8 bytes with Math.hypot.
                                                – nwellnhof
                                                Nov 7 at 19:44










                                              • @nwellnhof Ah, completely forgot about Math.hypot, which is perfect for this challenge! -20 bytes right there. Thanks. :)
                                                – Kevin Cruijssen
                                                Nov 7 at 20:27








                                              1




                                              1




                                              You can save at least 8 bytes with Math.hypot.
                                              – nwellnhof
                                              Nov 7 at 19:44




                                              You can save at least 8 bytes with Math.hypot.
                                              – nwellnhof
                                              Nov 7 at 19:44












                                              @nwellnhof Ah, completely forgot about Math.hypot, which is perfect for this challenge! -20 bytes right there. Thanks. :)
                                              – Kevin Cruijssen
                                              Nov 7 at 20:27




                                              @nwellnhof Ah, completely forgot about Math.hypot, which is perfect for this challenge! -20 bytes right there. Thanks. :)
                                              – Kevin Cruijssen
                                              Nov 7 at 20:27










                                              up vote
                                              1
                                              down vote













                                              Javascript, 245 bytes



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


                                              (Somewhat) more readable version:



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


                                              Just finds the bounding box, and tests each coordinate in that box for whether it's the best.



                                              I could save 8 bytes with an approximate answer, by replacing:



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






                                              share|improve this answer





















                                              • There are for sure more things to golf, but JS isn't my strong suite. Still, you can golf 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]}} to 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);. And I'm pretty sure you can remove the space at return[.
                                                – Kevin Cruijssen
                                                Nov 6 at 21:59






                                              • 1




                                                You can probably save a few bytes using Math.hypot.
                                                – nwellnhof
                                                Nov 7 at 19:48















                                              up vote
                                              1
                                              down vote













                                              Javascript, 245 bytes



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


                                              (Somewhat) more readable version:



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


                                              Just finds the bounding box, and tests each coordinate in that box for whether it's the best.



                                              I could save 8 bytes with an approximate answer, by replacing:



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






                                              share|improve this answer





















                                              • There are for sure more things to golf, but JS isn't my strong suite. Still, you can golf 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]}} to 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);. And I'm pretty sure you can remove the space at return[.
                                                – Kevin Cruijssen
                                                Nov 6 at 21:59






                                              • 1




                                                You can probably save a few bytes using Math.hypot.
                                                – nwellnhof
                                                Nov 7 at 19:48













                                              up vote
                                              1
                                              down vote










                                              up vote
                                              1
                                              down vote









                                              Javascript, 245 bytes



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


                                              (Somewhat) more readable version:



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


                                              Just finds the bounding box, and tests each coordinate in that box for whether it's the best.



                                              I could save 8 bytes with an approximate answer, by replacing:



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






                                              share|improve this answer












                                              Javascript, 245 bytes



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


                                              (Somewhat) more readable version:



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


                                              Just finds the bounding box, and tests each coordinate in that box for whether it's the best.



                                              I could save 8 bytes with an approximate answer, by replacing:



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







                                              share|improve this answer












                                              share|improve this answer



                                              share|improve this answer










                                              answered Nov 6 at 19:24









                                              Spitemaster

                                              1914




                                              1914












                                              • There are for sure more things to golf, but JS isn't my strong suite. Still, you can golf 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]}} to 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);. And I'm pretty sure you can remove the space at return[.
                                                – Kevin Cruijssen
                                                Nov 6 at 21:59






                                              • 1




                                                You can probably save a few bytes using Math.hypot.
                                                – nwellnhof
                                                Nov 7 at 19:48


















                                              • There are for sure more things to golf, but JS isn't my strong suite. Still, you can golf 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]}} to 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);. And I'm pretty sure you can remove the space at return[.
                                                – Kevin Cruijssen
                                                Nov 6 at 21:59






                                              • 1




                                                You can probably save a few bytes using Math.hypot.
                                                – nwellnhof
                                                Nov 7 at 19:48
















                                              There are for sure more things to golf, but JS isn't my strong suite. Still, you can golf 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]}} to 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);. And I'm pretty sure you can remove the space at return[.
                                              – Kevin Cruijssen
                                              Nov 6 at 21:59




                                              There are for sure more things to golf, but JS isn't my strong suite. Still, you can golf 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]}} to 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);. And I'm pretty sure you can remove the space at return[.
                                              – Kevin Cruijssen
                                              Nov 6 at 21:59




                                              1




                                              1




                                              You can probably save a few bytes using Math.hypot.
                                              – nwellnhof
                                              Nov 7 at 19:48




                                              You can probably save a few bytes using Math.hypot.
                                              – nwellnhof
                                              Nov 7 at 19:48










                                              up vote
                                              1
                                              down vote














                                              Ruby, 113 bytes





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


                                              Try it online!






                                              share|improve this answer



























                                                up vote
                                                1
                                                down vote














                                                Ruby, 113 bytes





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


                                                Try it online!






                                                share|improve this answer

























                                                  up vote
                                                  1
                                                  down vote










                                                  up vote
                                                  1
                                                  down vote










                                                  Ruby, 113 bytes





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


                                                  Try it online!






                                                  share|improve this answer















                                                  Ruby, 113 bytes





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


                                                  Try it online!







                                                  share|improve this answer














                                                  share|improve this answer



                                                  share|improve this answer








                                                  edited Nov 7 at 10:54

























                                                  answered Nov 7 at 10:43









                                                  G B

                                                  7,4261327




                                                  7,4261327






















                                                      up vote
                                                      1
                                                      down vote














                                                      Charcoal, 65 bytes



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


                                                      Try it online! Link is to verbose version of code. Explanation:



                                                      ≔Eθ§ι¹ζ


                                                      Get the y-coordinates into z.



                                                      ≔Eθ§ι⁰η


                                                      Get the x-coordinates into h.



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


                                                      Loop over the inclusive ranges from the minimums to the maximums of h and z generating the list of all potential disc centres.



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


                                                      Loop over all the disc centres, then loop over all of the original points, then loop over both coordinates, subtract, square, sum, take the maximum, and save the resulting list.



                                                      I§υ⌕η⌊η


                                                      Find the position of the minimal maximum diameter and print the corresponding disc centre.



                                                      I⌈X⌊η·⁵


                                                      Print the minimal maximum diameter, but round it up to the next integer.






                                                      share|improve this answer

























                                                        up vote
                                                        1
                                                        down vote














                                                        Charcoal, 65 bytes



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


                                                        Try it online! Link is to verbose version of code. Explanation:



                                                        ≔Eθ§ι¹ζ


                                                        Get the y-coordinates into z.



                                                        ≔Eθ§ι⁰η


                                                        Get the x-coordinates into h.



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


                                                        Loop over the inclusive ranges from the minimums to the maximums of h and z generating the list of all potential disc centres.



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


                                                        Loop over all the disc centres, then loop over all of the original points, then loop over both coordinates, subtract, square, sum, take the maximum, and save the resulting list.



                                                        I§υ⌕η⌊η


                                                        Find the position of the minimal maximum diameter and print the corresponding disc centre.



                                                        I⌈X⌊η·⁵


                                                        Print the minimal maximum diameter, but round it up to the next integer.






                                                        share|improve this answer























                                                          up vote
                                                          1
                                                          down vote










                                                          up vote
                                                          1
                                                          down vote










                                                          Charcoal, 65 bytes



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


                                                          Try it online! Link is to verbose version of code. Explanation:



                                                          ≔Eθ§ι¹ζ


                                                          Get the y-coordinates into z.



                                                          ≔Eθ§ι⁰η


                                                          Get the x-coordinates into h.



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


                                                          Loop over the inclusive ranges from the minimums to the maximums of h and z generating the list of all potential disc centres.



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


                                                          Loop over all the disc centres, then loop over all of the original points, then loop over both coordinates, subtract, square, sum, take the maximum, and save the resulting list.



                                                          I§υ⌕η⌊η


                                                          Find the position of the minimal maximum diameter and print the corresponding disc centre.



                                                          I⌈X⌊η·⁵


                                                          Print the minimal maximum diameter, but round it up to the next integer.






                                                          share|improve this answer













                                                          Charcoal, 65 bytes



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


                                                          Try it online! Link is to verbose version of code. Explanation:



                                                          ≔Eθ§ι¹ζ


                                                          Get the y-coordinates into z.



                                                          ≔Eθ§ι⁰η


                                                          Get the x-coordinates into h.



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


                                                          Loop over the inclusive ranges from the minimums to the maximums of h and z generating the list of all potential disc centres.



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


                                                          Loop over all the disc centres, then loop over all of the original points, then loop over both coordinates, subtract, square, sum, take the maximum, and save the resulting list.



                                                          I§υ⌕η⌊η


                                                          Find the position of the minimal maximum diameter and print the corresponding disc centre.



                                                          I⌈X⌊η·⁵


                                                          Print the minimal maximum diameter, but round it up to the next integer.







                                                          share|improve this answer












                                                          share|improve this answer



                                                          share|improve this answer










                                                          answered Nov 8 at 21:30









                                                          Neil

                                                          77.6k744174




                                                          77.6k744174






























                                                               

                                                              draft saved


                                                              draft discarded



















































                                                               


                                                              draft saved


                                                              draft discarded














                                                              StackExchange.ready(
                                                              function () {
                                                              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f175405%2fsmallest-integer-disk%23new-answer', 'question_page');
                                                              }
                                                              );

                                                              Post as a guest




















































































                                                              Popular posts from this blog

                                                              Guess what letter conforming each word

                                                              Port of Spain

                                                              Run scheduled task as local user group (not BUILTIN)