가장 작은 정수 디스크 좌표 점의 목록이 될 것입니다 x및

이 과제는 특정 지점이 포함 된 가장 작은 디스크를 찾는 것입니다. 그러나이 도전에서는 디스크의 좌표와 반지름이 모두 정수 여야한다는 사실에 의해 다소 까다로워집니다.

귀하의 입력은 정수 좌표 점의 목록이 될 것입니다 xy. 이것을 튜플 목록, 목록 목록 또는 쌍 모음을 나타내는 다른 방법으로 사용할 수 있습니다. x그리고 y둘 다 정수일 것입니다. 모든 포인트는 고유하며 적어도 하나의 포인트가 있습니다.

귀하의 출력은 세 개의 숫자의 형태로 디스크 것 X, Y하고 R. X, Y그리고 R모든 정수는, XY디스크의 센터를 대표하고 R그 반경을 나타냅니다. 모든 주어진 점과 중심 사이의 거리는보다 작거나 같아야하며 R, R이 조건을 만족 하는 더 작은 디스크가 없어야합니다 .

주어진 입력에 대해 여러 가지 가능한 솔루션이있을 수 있습니다.이 경우 코드는 적어도 하나의 솔루션을 출력해야합니다.

언어가 지원하는 모든 종류의 지오메트리 내장 기능을 사용할 수 있으며 입력 / 출력은 숫자 대신 내장 포인트 / 디스크 객체를 통해 이루어질 수 있습니다.

테스트 사례

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

가장 적은 바이트가 이깁니다.



답변

젤리 , 25 24 22 21 20 18 바이트

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

에 대해 알려주고 )1 바이트를 절약 한 @EriktheOutgolfer에게 감사드립니다 .

2 바이트를 절약 한 @Dennis에게 감사합니다.

온라인으로 사용해보십시오!

설명

«/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 바이트

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

온라인으로 사용해보십시오!

이 프로그램은 쓰기가 쉬웠다 – Brachylog는 이런 종류의 문제에 거의 완벽하지만 골프하기는 어렵다. 내가 효과가있는 것 같지 않은 것처럼 여기에 어딘가에 바이트를 저장 한 경우 놀라지 않을 것입니다 (그리고 중첩 된지도 명령, 일반적으로 회원 / 핀을 사용해야한다는 표시가 포함되어 있지만, 할 수는 없습니다) 방법을 참조하십시오).

이것은 기능 제출입니다. 입력은 형식에서 왼쪽 인수부터 함수까지[[x,y],[x,y],…] 의 오른쪽 인수에서 출력[r,[[x,y]]] . (입력에서 음수를 사용 _하려면 Brachylog가 빼기 기호가 아닌을 사용한다는 점에 유의하십시오 -. Brachylog와 함께 제공되는 함수 → 전체 프로그램 랩퍼가 명령 행 인수를 사용하여 요청 하면 음수가 표시 되므로 혼동 Z됩니다. 에서 출력 정규 마이너스 기호.)

설명

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

Brachylog에 특정 속성 값 (이 경우에는 중심점을 중심으로 한 디스크 반경)을 찾도록 요청한다는 점에서 흥미 롭습니다. A 모든 입력 지점에 맞는 을 하지만 요구 사항을 거의 적용하지 않는다는 반지름은 숫자입니다). 그러나 Brachylog는 콘크리트 숫자를 사용하지 않고 내부적으로 문제의 반지름을 상징적으로 계산하므로 최종 값에 도달하면 두 가지 작업을 한 번에 수행합니다. 먼저 좌표 A와 반지름에 정수만 사용되도록합니다. (제곱 반지름을 제곱수로 강제하고 ≤ᵛ“최대 값 이상”을 찾는 사용법을 설명 ); 둘째, 가능한 가장 작은 가능한 반경을 찾습니다 (반지름이 출력에서 ​​첫 번째가 됨).

프로그램에서 지정되지 않은 한 가지는 모든 포인트가 디스크의 동일한 중심에 대해 측정된다는 것입니다. 작성된 바와 같이, 우리는 각 지점마다 다른 중심을 사용하지 않는다는 제약이 없습니다. 그러나 순위 결정 순서 (이 경우 세 번째에 의해 설정 됨) 구조 제약 조건이 값 제약 조건이 암시하기 전에 평가됨) )는 A가능한 한 짧아야합니다 (예 : 단일 요소이므로 동일한 요소를 사용함) 매번 중앙에; 그것은 A먼저 길이가 0을 시도 하지만 분명히 작동하지 않으므로 다음에 싱글 톤 목록을 시도하십시오). 결과적으로, 우리는 “무료”라는 유용한 제약 (하나의 디스크 만 가지고 있음)을 얻게됩니다.

이 솔루션 은 소스 코드를 변경하지 않고 여러 차원으로 일반화 합니다. 여기에는 사물이 2 차원이라는 가정이 없습니다. 따라서 가장 작은 정수 영역이 필요한 경우에도 마찬가지입니다.


답변

펄 6 , 81 바이트

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

온라인으로 사용해보십시오!

점리스트를 2 요소리스트로 취합니다 ((X1, Y1), (X2, Y2), ...). 리스트를 돌려 (R, (X, Y))줍니다. Pietu1998의 Jelly 답변과 동일한 접근 방식을 사용합니다.

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

minmax메소드는 다음을 반환하므로 유용합니다.Range . 범위의 데카르트 곱은 정수 좌표를 가진 모든 점을 직접 산출합니다.


답변

05AB1E , 26 바이트

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

@ Pietu1998 포트 의 젤리 답변 .

온라인으로 시도 하거나 모든 테스트 사례를 확인하십시오 .

설명:

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

답변

Matlab, 73 바이트

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

가장 작은 솔루션 (부동 소수점)을 찾아 가장 가까운 점으로 반올림하고 반지름을 좁 힙니다 (minimax 문제의 경우 최악). 그것이 가능한 모든 경우 (정확도 내)에 올바른 솔루션을 제공하는지 확실하지 않지만 테스트 사례에서는 입력 오류가 발생하지 않으면 작동합니다.

전화 해

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

답변

Pyth , 34 33 바이트

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

출력 형태 [R,x,y]

여기 에서 온라인으로 시도 하거나 모든 테스트 사례를 한 번에 확인 하십시오 .

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

편집 : 이전 버전의 출력 형식을 재정렬하여 바이트를 저장했습니다.

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


답변

Wolfram Language (Mathematica) , 66 바이트

다음은 무차별 대입 방식입니다. 훨씬 짧은 BoundingRegion[#,"MinDisk"]&함수를 고려 했지만 정수 좌표 및 반경을 강제로 지정할 방법이 없습니다.

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

온라인으로 사용해보십시오!