Tantangan ini adalah tentang menemukan disk terkecil yang berisi beberapa poin tertentu. Ini dibuat agak rumit, oleh kenyataan bahwa dalam tantangan ini, koordinat disk dan jari-jari keduanya harus bilangan bulat.

Input Anda akan menjadi daftar poin dengan koordinat bilangan bulat xdan y. Anda dapat mengambil ini sebagai daftar tupel, daftar daftar, atau cara lain untuk mewakili kumpulan pasangan. xdan ykeduanya akan (mungkin negatif) bilangan bulat. Setiap poin dijamin unik, dan akan ada setidaknya satu poin.

Output Anda akan menjadi disk dalam bentuk tiga angka, X, Y, dan R. X,, Ydan Rsemuanya bilangan bulat, Xdan Ymewakili pusat disk dan Rmewakili radiusnya. Jarak antara setiap titik dan pusat harus kurang dari atau sama dengan R, dan tidak boleh ada disk dengan yang lebih kecil Ryang juga memenuhi kondisi ini.

Ada kemungkinan bahwa akan ada beberapa solusi yang mungkin untuk input yang diberikan, kode Anda harus menampilkan setidaknya satu dari mereka dalam hal ini.

Anda dapat menggunakan segala jenis geometri bawaan dalam dukungan bahasa Anda jika ada, dan input / output mungkin melalui objek titik / disk bawaan bukan hanya angka.

Uji Kasus

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)

Bytes paling sedikit menang.

Jelly , 25 24 22 21 20 18 byte

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

Terima kasih kepada @EriktheOutgolfer karena memberi tahu saya ), menghemat 1 byte.

Terima kasih kepada @Dennis karena telah menghemat 2 byte.

Cobalah online!

Penjelasan

«/r»/Œpµ³_²§½ṀĊ,)Ṃ      Main link. Arg: points
                        e.g. [[1,4],[3,2],[3,1]]
«/                      Find minimums by coordinate
                        e.g. [1,1]
   »/                   Find maximums by coordinate
                        e.g. [3,4]
  r                     Inclusive ranges by coordinate
                        e.g. [[1,2,3],[1,2,3,4]]
     Œp                 Cartesian product of the x and y ranges
                        e.g. [[1,1],[1,2],[1,3],[1,4],...,[3,4]]
       µ                    Chain, arg: center
                            e.g. [1,3]
        ³                   Get the original points
                            e.g. [[1,4],[3,2],[3,1]]
         _                  Subtract the center from each
                            e.g. [[0,1],[2,-1],[2,-2]]
          ²                 Square each number
                            e.g. [[0,1],[4,1],[4,4]]
           §                Sum each sublist
                            e.g. [1,5,8]
            ½               Square root of each number
                            e.g. [1,2.24,2.83]
             Ṁ              Find the maximum
                            e.g. 2.83
              Ċ             Round up
                            e.g. 3
               ,            Pair with the center point
                            e.g. [3,[1,3]]
                )       Do the above for all points
                        e.g. [[3,[1,1]],[3,[1,2]],[3,[1,3]],...,[3,[3,4]]]
                 Ṃ      Find the lexicographically smallest pair
                        e.g. [3,[1,1]]

Brachylog v2, 19 byte

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

Cobalah online!

Program ini mudah ditulis - Brachylog hampir sempurna untuk masalah seperti ini - tetapi sulit untuk bermain golf. Tidak akan mengejutkan saya jika ada penghematan byte di suatu tempat di sini, karena beberapa hal yang saya lakukan tampaknya memiliki efek (dan itu berisi instruksi peta bersarang, biasanya tanda bahwa Anda harus menggunakan anggota / findall, tetapi saya tidak bisa lihat cara untuk melakukannya).

Ini adalah pengiriman fungsi. Input dari argumen kiri ke fungsi dalam format [[x,y],[x,y],…], output dari argumen kanan dalam formulir [r,[[x,y]]]. (Jika Anda ingin mencoba angka negatif dalam input, perhatikan bahwa Brachylog menggunakan _untuk tanda minus, tidak -. Ini membingungkan karena fungsi → pembungkus program lengkap yang dikirimkan oleh Brachylog, diminta menggunakan argumen baris perintah Z, akan menampilkan angka negatif dalam output dengan tanda minus reguler.)

Penjelasan

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

Ini menarik karena kami meminta Brachylog untuk menemukan nilai properti tertentu (dalam hal ini, jari-jari disk terpusat pada titik Ayang cocok dengan semua titik input), tetapi sulit menempatkan persyaratan apa pun di atasnya (yang kami butuhkan hanyalah bahwa jari-jari adalah angka). Namun, Brachylog secara internal akan menghitung jari-jari yang dimaksud secara simbolis daripada mencoba menggunakan angka konkret, jadi ketika final ≜tercapai, ia menyelesaikan dua hal sekaligus: pertama, itu memastikan bahwa hanya bilangan bulat yang digunakan untuk koordinat Adan untuk jari-jari (memaksa jari-jari kuadrat menjadi angka kuadrat, dan menjelaskan penggunaan ≤ᵛuntuk menemukan "maksimum atau lebih besar"); kedua, ia menemukan jari-jari paling layak yang mungkin ada (karena jari-jari lebih dulu dalam output).

Satu hal yang tidak ditentukan dalam program sama sekali adalah bahwa semua titik diukur terhadap pusat disk yang sama; seperti yang tertulis, tidak ada kendala bahwa kami tidak menggunakan pusat yang berbeda untuk setiap poin. Namun, urutan tiebreak (yang dalam hal ini ditetapkan oleh yang ketiga ᵐ, dan yang sebagai batasan struktur akan dievaluasi sebelum batasan nilai yang disiratkan oleh ≜) ingin Asesingkat mungkin (yaitu elemen tunggal, jadi kami menggunakan yang sama pusat setiap kali; ia mencoba panjang nol Apertama tapi itu jelas tidak berhasil, jadi coba daftar singleton berikutnya). Akibatnya, kami akhirnya mendapatkan kendala yang berguna (bahwa kami hanya memiliki satu disk) "gratis".

Solusi ini terjadi untuk menggeneralisasi ke sejumlah dimensi , tanpa perubahan pada kode sumber; tidak ada asumsi di sini bahwa benda itu dua dimensi. Jadi jika Anda membutuhkan bola integer terkecil, Anda dapat memilikinya juga.

Perl 6 , 81 byte

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

Cobalah online!

Mengambil daftar poin sebagai daftar 2-elemen ((X1, Y1), (X2, Y2), ...). Mengembalikan daftar (R, (X, Y)). Menggunakan pendekatan yang sama dengan jawaban Jelly Pietu1998:

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

The minmaxMetode ini berguna di sini seperti mengembalikan Range. Produk Cartesian dari rentang langsung menghasilkan semua titik dengan koordinat bilangan bulat.

05AB1E , 26 byte

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

Port dari jawaban Jelly @ Pietu1998 .

Cobalah secara online atau verifikasi semua kasus uji .

Penjelasan:

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

Matlab, 73 byte

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

Cukup temukan solusi terkecil (titik apung) dan bulatkan ke titik terdekat dan potong jari-jarinya (kasus terburuk untuk masalah minimax). Saya tidak tahu pasti apakah itu menghasilkan solusi yang benar untuk semua kasus yang mungkin (dalam presisi), tetapi untuk kasus uji itu harus bekerja (jika saya tidak membuat kesalahan pengetikan).

Sebut saja dengan

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

Pyth , 34 33 byte

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

Output dalam bentuk [R,x,y]

Coba online di sini , atau verifikasi semua uji sekaligus di sini .

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

Sunting: Menyimpan byte dengan mengatur ulang format output, versi sebelumnya:

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

Bahasa Wolfram (Mathematica) , 66 byte

Inilah pendekatan brute force. Saya menganggap fungsi jauh lebih pendek BoundingRegion[#,"MinDisk"]&tetapi tidak ada cara untuk memaksa koordinat bilangan bulat & jari-jari.

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

Cobalah online!

Java 10, 283 279 277 257 byte

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 byte berkat tip penggunaan @nwellnhofMath.hypot .

Array hasil berada dalam urutan [R,X,Y].

Cobalah online.

Penjelasan:

C->{                  // Method with 2D int-array as parameter & int-array as return-type
  int M=1<<31,        //  Minimum `M`, starting at -2,147,483,648
      m=M,            //  Temp integer, starting at -2,147,483,648 as well
      X=M,            //  Largest X coordinate, starting at -2,147,483,648 as well
      Y=M,            //  Largest Y coordinate, starting at -2,147,483,648 as well
      x=M-1,          //  Smallest X coordinate, starting at 2,147,483,647
      y=x,            //  Smallest Y coordinate, starting at 2,147,483,647 as well
      t,a,            //  Temp integers, starting uninitialized
      r[]={x};        //  Result-array, starting at one 2,147,483,647
  for(var c:C){       //  Loop over the input-coordinates
    x=(t=c[0])<x?t:x; //   If the X coordinate is smaller than `x`, change it
    X=t>X?t:X;        //   If the X coordinate is larger than `X`, change it
    y=(t=c[1])<y?t:y; //   If the Y coordinate is smaller than `y`, change it
    Y=t>Y?t:Y;}       //   If the Y coordinate is larger than `Y`, change it
 for(;y<=Y;y++)       //  Loop `y` in the range [`y`,`Y`]:
   for(t=x;t<=X       //   Inner loop `t` in the range [`x`,`X`]:
          ;           //     After every iteration:
           r=m<r[0]?  //      If `m` is smaller than the first value:
              new int[]{m,t,y}
                      //       Replace the result with `m,t,y`
             :        //      Else:
              r,      //       Leave `r` unchanged
           m=M,       //      Reset `m` to -2,147,483,648 for the next iteration
           t++)       //      And increase `t` by 1
     for(var c:C)     //    Inner loop over the input-coordinates
       m=(a=(int)Math.ceil(Math.hypot(c[0]-t,c[1]-y)))
                      //     Subtract `t` from the X coordinate;
                      //     subtract `y` from the Y coordinate;
                      //     take the hypot (<- sqrt(x*x+y*y)) of those
                      //     ceil it
                      //     And set `a` to this value
          >m?         //     If `a` is larger than `m`:
           a          //      Set `m` to `a`
          :           //     Else:
           m;         //      Leave `m` unchanged
  return r;}          //  Return the result `r`

Javascript, 245 byte

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

(Agak) versi yang lebih mudah dibaca:

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

Temukan saja kotak pembatas, dan uji setiap koordinat dalam kotak itu untuk mengetahui apakah itu yang terbaik.

Saya bisa menyimpan 8 byte dengan jawaban perkiraan, dengan mengganti:

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

Ruby , 113 byte

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

Cobalah online!

Arang , 65 byte

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

Cobalah online!Tautan adalah untuk mengucapkan versi kode. Penjelasan:

≔Ｅθ§ι¹ζ

Dapatkan koordinat y z .

≔Ｅθ§ι⁰η

Dapatkan koordinat x ke h .

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

Putaran atas rentang inklusif dari minimum ke maksimum hdanz menghasilkan daftar semua pusat disk yang potensial.

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

Ulangi semua pusat cakram, lalu putar semua titik awal, lalu lewati kedua koordinat, kurangi, kuadrat, jumlah, ambil maksimum, dan simpan daftar yang dihasilkan.

Ｉ§υ⌕η⌊η

Temukan posisi diameter maksimum minimal dan cetak pusat disk yang sesuai.

Ｉ⌈Ｘ⌊η·⁵

Cetak diameter maksimum minimal, tetapi bulatkan ke bilangan bulat berikutnya.