회전 된 사각형의 치수 결정 절대로 그리드 경계를

이 스택 스 니펫 은 치수, 위치, 각도 및 그리드 치수에 대한 매개 변수가 지정된 검은 색 배경에 별명을 가진 흰색 직사각형을 그립니다 .

<style>html *{font-family:Consolas,monospace}input{width:24pt;text-align:right;padding:1px}canvas{border:1px solid gray}</style><p>grid w:<input id='gw' type='text' value='60'> grid h:<input id='gh' type='text' value='34'> w:<input id='w' type='text' value='40'> h:<input id='h' type='text' value='24'> x:<input id='x' type='text' value='0'> y:<input id='y' type='text' value='0'> &theta;:<input id='t' type='text' value='12'>&deg; <button type='button' onclick='go()'>Go</button></p>Image<br><canvas id='c'>Canvas not supported</canvas><br>Text<br><textarea id='o' rows='36' cols='128'></textarea><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><script>function toCart(t,a,n,r){return{x:t-n/2,y:r/2-a}}function vtx(t,a,n){return{x:n.x+t*Math.cos(a),y:n.y+t*Math.sin(a)}}function sub(t,a){return{x:t.x-a.x,y:t.y-a.y}}function dot(t,a){return t.x*a.x+t.y*a.y}function inRect(t,a,n,r){var e=sub(a,t),o=sub(a,n),l=sub(a,r),i=dot(e,o),v=dot(e,l);return i>0&&i<dot(o,o)&&v>0&&v<dot(l,l)}function go(){var t=parseInt($("#gw").val()),a=parseInt($("#gh").val()),n=parseFloat($("#w").val()),r=parseFloat($("#h").val()),e={x:parseFloat($("#x").val()),y:parseFloat($("#y").val())},o=Math.PI*parseFloat($("#t").val())/180,l=Math.sqrt(n*n+r*r)/2,i=Math.atan2(r,n),v=vtx(l,o+i,e),h=vtx(l,o+Math.PI-i,e),u=vtx(l,o-i,e),x=$("#c");x.width(t).height(a).prop({width:t,height:a}),x=x[0].getContext("2d");for(var s="",c=0;a>c;c++){for(var f=0;t>f;f++)inRect(toCart(f+.5,c+.5,t,a),v,h,u)?(s+="..",x.fillStyle="white",x.fillRect(f,c,1,1)):(s+="XX",x.fillStyle="black",x.fillRect(f,c,1,1));a-1>c&&(s+="\n")}$("#o").val(s)}$(go)</script>

스 니펫 확장

( JSFiddle 버전 )

텍스트 표현은 XX이미지에 검은 색 픽셀이있는 ..곳 과 흰색 픽셀이있는 곳마다 있습니다. (그들이 경우 찌그러 외모 X와 ..)

스 니펫에서 생성 된 사각형의 텍스트 표현을 취하고 사각형의 대략적인 너비와 높이를 실제 너비와 높이의 ± 7 % 이내로 출력하는 프로그램을 작성하십시오 .

프로그램은 다음과 같은 제약 조건으로 스 니펫으로 그릴 수있는 모든 가능한 사각형을 효과적으로 작동해야합니다.

  • 사각형 너비와 높이는 최소 24입니다.
  • 격자 너비와 높이는 최소 26입니다.
  • 사각형은 절대로 그리드 경계를 건드 리거나 벗어나지 않습니다.

따라서 입력 사각형에는 회전, 위치 및 치수가있을 수 있으며 위의 세 가지 제약 조건이 충족되는 한 그리드의 치수가 달라질 수 있습니다. 격자 치수를 제외하고 스 니펫 매개 변수는 부 동일 수 있습니다.

세부

  • 원시 텍스트 사각형을 입력으로 사용하거나 원시 텍스트 사각형을 포함하는 파일의 파일 이름 (stdin 또는 명령 행을 통해)을 사용하십시오. 텍스트 사각형에 줄 바꿈 문자가 있다고 가정 할 수 있습니다.
  • 텍스트 사각형이 and가 아닌 다른 두 개의 인쇄 가능한 ASCII 문자 로 만들어 진다고 가정 할 수 있습니다.X. 원하는 경우. 줄 바꿈은 줄 바꿈을 유지해야합니다.
  • 측정 된 폭과 높이를 정수로 출력하거나 어떤 순서로 stdout에 띄우십시오 (어느 것이 어떤 매개 변수와 함께 실제로 어떤 것인지 결정하는 방법이 없기 때문에). 분명히이 두 차원을 보여주고 있음을 모든 형식은 좋은 예이다 D1 D2, D1,D2, D1\nD2,(D1, D2) , 등
  • 프로그램 대신 텍스트 사각형을 문자열 또는 파일 이름으로 사용하여 결과를 정상적으로 인쇄하거나 두 요소가 포함 된 문자열 또는 목록 / 튜플로 반환하는 함수를 작성할 수 있습니다.
  • 그 기억 XX또는 ..직사각형의 하나의 ‘픽셀’이 아닌이있다.

예

전의. 1

매개 변수 : grid w:60 grid h:34 w:40 h:24 x:0 y:0 θ:12(스 니펫 기본값)

입력

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX....XXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX............XXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX........................XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..................................XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX............................................XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX....................................................XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..............................................................XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX..........................................................................XXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX................................................................................XXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX................................................................................XXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX..................................................................................XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX..........................................................................XXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX..............................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX....................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX............................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX..................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX........................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXX............XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXX....XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

출력 예

  • 40 24
  • 24 40
  • [40.0, 24.0]
  • 42.8, 25.68 (+ 7 %)
  • 37.2, 22.32 (-7 %)

전의. 2

매개 변수 : grid w:55 grid h:40 w:24.5 h:24 x:-10.1 y:2 θ:38.5

입력

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX......XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX............XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..............XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXX..................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXX......................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX............................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..............................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX......................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXX............................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXX................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXX..................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXX......................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XX............................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XX..............................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XX................................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXX..............................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXX..............................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXX............................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXX......................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXX....................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXX................................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXX............................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX......................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX..................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX................................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXX..........................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXX......................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX..................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX................XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXX..........XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXX......XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

출력 예

  • 24.0 24.5
  • 25.68 26.215 (+ 7 %)
  • 22.32 22.785 (-7 %)

채점

바이트 단위의 가장 짧은 코드가 이깁니다. Tiebreaker는 최고 투표 게시물입니다.

답변

Matlab, 226 바이트

아이디어는 간단합니다. 먼저 사각형이 얼마나 많이 회전했는지 확인한 다음 사각형이 똑바로되도록 이미지를 적절하게 돌립니다. 그런 다음 행 열의 모든 픽셀을 따로 ‘합계’하고 너비와 높이를 결정하기 위해 평균 (간단한 임계 값)보다 많은 합계를 계산하십시오. 이 간단한 방법은 놀랍도록 안정적으로 작동합니다.

각도를 어떻게 감지합니까?

나는 각 단계 (각각 1도)를 시도하고 열을 따라 합계하고 합계 벡터를 얻습니다. 사각형이 똑바로있을 때 이상적 으로이 합계 벡터에서 두 가지 갑자기 변경되는 것이 이상적입니다. 사각형이 팁 위에 있으면 변경이 매우 점진적입니다. 그래서 나는 첫 번째 미분을 사용하고 ‘점프’의 수를 최소화하려고합니다. 여기서 우리가 최소화하려는 기준의 도표를 볼 수 있습니다. 네 가지 가능한 수직 방향에 해당하는 네 가지 최소값을 볼 수 있습니다.

최소화 기준

추가 생각 : 철저한 각도 검색에 많은 문자가 필요하기 때문에 얼마나 많은 골프를 칠 수 있는지 확실하지 않으며 내장 된 최적화 방법을 사용하면 달성 할 수 있을지 의심됩니다. 우리가 찾고 있지 않은 당신은 쉽게 각도 작은 스텝 크기를 선택하여 (큰 사진의) 정확도를 개선하고 대체 할 수 있도록에만 360 ° 대신에 90 °를 검색 할 수 있습니다 0:360와 0:.1:90그런 somehting 나. 그러나 어쨌든 도전은 골프보다는 강력한 알고리즘을 찾는 것이 더 어려웠으며 골프 언어의 항목이 내 제출을 훨씬 뒤에 남겨 놓을 것이라고 확신합니다. =)

추신 : 누군가 Matlab / Octave에서 골프 언어를 파생시켜야합니다.

출력

예 1 :

 25    39

예 2 :

 25    24

암호

골프 :

s=input('');r=sum(s=='n');S=reshape(s',nnz(s)/r,r)';S=S(:,1:2:end-2)=='.';m=Inf;a=0;for d=0:360;v=sum(1-~diff(sum(imrotate(S,d))));if v<m;m=v;a=d;end;end;S=imrotate(S,a);x=sum(S);y=sum(S');disp([sum(x>mean(x)),sum(y>mean(y))])

언 골프 드 :

s=input('');
r=sum(s=='n');
S=reshape(s',nnz(s)/r,r)';
S=S(:,1:2:end-2)=='.';
m=Inf;a=0;
for d=0:360;
    v=sum(1-~diff(sum(imrotate(S,d))));
    if v<m;
        m=v;a=d;
    end;
end;
S=imrotate(S,a);
x=sum(S);y=sum(S');
disp([sum(x>mean(x)),sum(y>mean(y))])

답변

CJam, 68 65 64 바이트

이것은 조금 더 골프를 칠 수 있습니다 ..

qN/2f%{{:QN*'.#Qz,)mdQ2$>2<".X"f#_~>@@0=?Qz}2*;@@-@@-mhSQWf%}2*;

작동 원리

당신이 그것에 대해 생각하면 논리는 매우 간단합니다.

입력 X.조합 에서 필요한 것은 두 개의 인접한 변의 3 좌표입니다. 우리가 그들을 얻는 방법은 다음과 같습니다.

First

사각형의 모든 방향 .에서 입력 전체의 첫 번째 는 모서리 중 하나가됩니다. 예를 들어 ..

XXXXXXXXXXXXXX
XXXXXXX...XXXX
XXXX.......XXX
X............X
XX.........XXX
XXXX...XXXXXXX
XXXXXXXXXXXXXX

여기서 첫 번째 .는 두 번째 줄, 8 번째 열에 있습니다.

그러나 그것은 아닙니다. 우리는 .조정을하고 오른쪽 끝의 좌표를 얻기 위해 해당 라인 의 런 너비를 좌표에 추가해야합니다.

Second

위의 사각형을 바꾸면 (개행으로 피벗) 왼쪽 아래 모서리가 위 단계를 대신합니다. 그러나 여기서 우리는 .어쨌든 가장자리의 왼쪽 아래 좌표를 얻고 싶을 때 실행 길이를 보상하지 않습니다 (조옮김 형태는 여전히 처음으로 발생합니다 .)

Rest two

두 좌표를 쉬려면 직사각형을 가로로 뒤집어 위의 두 단계를 수행하십시오. 여기 모퉁이 중 하나는 처음 두 개에서 공통입니다.

4를 모두 얻은 후에는 간단한 수학을 수행하여 거리를 얻습니다.

이제 이것은 가장 정확한 방법은 아니지만 오류 여백 내에서와 사각형의 가능한 모든 방향에서 잘 작동합니다.

코드 확장 (비트 구식)

qN/2f%{{:QN*'.#Q0=,)md}:A~1$Q='.e=+QzA@@-@@-mhSQWf%}2*;
qN/2f%                               e# Read the input, split on newlines and squish it
      {   ...   }2*                  e# Run the code block two times, one for each side
{:QN*'.#Q0=,)md}:A~                  e# Store the code block in variable A and execute it
 :QN*                                e# Store the rows in Q variable and join by newlines
     '.#                             e# Get the location of the first '.'
        Q0=,)                        e# Get length + 1 of the first row
             md                      e# Take in X and Y and leave out X/Y and X%Y on stack
1$Q=                                 e# Get the row in which the first '.' appeared
    '.e=+                            e# Get number of '.' in that row and add it to X%Y
         QzA                         e# Transpose the rows and apply function A to get
                                     e# the second coordinate
            @@-@@-                   e# Subtract resp. x and y coordinates of the two corners
                  mh                 e# Calculate (diff_x**2 + diff_y**2)**0.5 to get 1 side
                    SQWF%            e# Put a space on stack and put the horizontally flipped
                                     e# version of the rows/rectangle all ready for next two
                                     e# coordinates and thus, the second side

여기에서 온라인으로 사용해보십시오

답변

파이썬 3, 347 337 바이트

이것은 내가 예상했던 것보다 더 힘들었습니다. 진행중인 작업…

def f(s):
 l=s.split('\n');r=range;v=sorted;w=len(l[0]);h=len(l);p=[[x,y]for x in r(w)for y in r(h)if'X'>l[y][x]];x,y=[sum(k)/w/h for k in zip(*p)];g=[[x/2,y]];d=lambda a:((a[0]/2-a[2]/2)**2+(a[1]-a[3])**2)**.5
 for i in r(3):g+=v(p,key=lambda c:~-(c in g)*sum(d(j+c)for j in g))[:1]
 print(v(map(d,[g[1]+g[2],g[2]+g[3],g[1]+g[3]]))[:2])

f문자열을 인수로 사용하고 결과를 STDOUT에 인쇄 하는 함수 를 정의합니다 .

Pyth, 87 84 82 81 75 72 71 바이트

(아마도 집에 도착했을 때, 부정확하고 조사 중)

Km%2d.zJf<@@KeThTG*UhKUKPSm.adfqlT2ytu+G]ho*t}NGsm.a,kNGJ3]mccsklhKlKCJ

방법은 아직 너무 오래. 기본적으로 이전 포트입니다. Pyth의 .a유클리드 거리를 사랑합니다 . STDIN을 통해 입력을 가져오고 STDOUT을 통해 출력을 제공합니다. 사각형이 아닌 문자가 소문자 일 것으로 예상됩니다 x(물론 ASCII 값 98 이상의 모든 것).

연산

둘 다 동일한 알고리즘을 사용합니다. 기본적으로 사각형 영역의 질량 중심을 포함하는 배열로 시작합니다. 그런 다음 사각형의 모든 점의 배열에 3 개의 점을 추가하고 항상 배열에있는 점까지의 최대 거리 를 가진 점을 선택합니다 . 결과는 항상 사각형의 다른 구석에 세 점입니다. 그런 다음 세 점 사이의 세 거리를 모두 계산하고 가장 짧은 두 거리를 가져옵니다.

답변

파이썬 2, 342 바이트

import sys
r=[]
h=.0
for l in sys.stdin:w=len(l);r+=[[x*.5,h]for x in range(0,w,2)if l[x:x+2]=='..'];h+=1
x,y=.0,.0
for p in r:x+=p[0];y+=p[1]
n=len(r)
x/=n
y/=n
m=.0
for p in r:
 p[0]-=x;p[1]-=y;d=p[0]**2+p[1]**2
 if d>m:m=d;u,v=p
m=.0
for p in r:
 d=p[0]*v-p[1]*u
 if d>m:m=d;s,t=p
print ((u-s)**2+(v-t)**2)**.5+1,((u+s)**2+(v+t)**2)**.5+1

이것은 @ Pietu1998의 알고리즘에서 영감을 얻었습니다. 하나의 모퉁이를 중심에서 가장 먼 지점으로 결정하는 아이디어가 필요하지만 거기에서 다릅니다.

  • 두 번째 모서리를 중심에서 첫 번째 모서리까지 벡터가있는 가장 큰 교차 곱이있는 점으로 결정합니다. 이것은 중심에서 첫 번째 모서리까지의 선에서 가장 큰 거리를 가진 점을 제공합니다.
  • 세 번째 모서리는 중앙을 기준으로 두 번째 모서리의 미러 이미지이므로 검색 할 필요가 없습니다.

따라서 코드는 다음 순서를 따릅니다.

  • 첫 번째 루프는 입력의 선 위에 있으며 r사각형 점 목록 을 작성합니다 .
  • 두 번째 루프는 사각형의 중심을 제공하여 모든 사각형 점의 평균을 계산합니다.
  • 세 번째 루프는 중심에서 가장 먼 지점을 찾습니다. 이것이 첫 번째 코너입니다. 동시에 점 좌표가 나머지 계산의 중심을 기준으로 목록의 점에서 중심을 뺍니다.
  • 네 번째 루프는 벡터가 첫 번째 모서리에있는 가장 큰 교차 곱이있는 점을 찾습니다. 이것은 두 번째 코너입니다.
  • 첫 번째 모서리와 두 번째 모서리 사이의 거리와 첫 번째 모서리와 두 번째 모서리의 미러 이미지 사이의 거리를 인쇄합니다.
  • 1.0원래 거리 계산에는 픽셀 인덱스가 사용되므로 거리에 추가됩니다. 예를 들어, 5 개의 픽셀이있는 경우 마지막 픽셀과 첫 번째 픽셀의 인덱스 차이는 4에 불과하므로 최종 결과에서 보상이 필요합니다.

정밀도는 아주 좋습니다. 두 가지 예를 들면 다음과 같습니다.

$ cat rect1.txt | python Golf.py
24.5372045919 39.8329756779
$ cat rect2.txt | python Golf.py
23.803508502 24.5095563412

답변

파이썬 2, 272 바이트

이전 알고리즘과 완전히 다른 알고리즘이므로 별도의 답변으로 게시하십시오.

import sys,math
y,a,r=0,0,0
l,t=[1<<99]*2
for s in sys.stdin:
 c=s.count('..')
 if c:a+=c;x=s.find('.')/2;l=min(l,x);r=max(r,x+c);t=min(t,y);b=y+1
 y+=1
r-=l
b-=t
p=.0
w,h=r,b
while w*h>a:c=math.cos(p);s=math.sin(p);d=c*c-s*s;w=(r*c-b*s)/d;h=(b*c-r*s)/d;p+=.001
print w,h

이 방법은 모서리를 전혀 식별하지 않습니다. 경계 상자의 크기 (너비와 높이)와 회전 된 사각형의 영역이 사각형의 너비와 높이를 결정하기에 충분하다는 관찰 결과를 기반으로합니다.

스케치를 보면 사각형의 크기 / 크기 및 회전 각도 를 사용하여 경계 상자 의 너비 ( wb) 및 높이 ( hb) 를 계산하는 것이 매우 쉽습니다 .whp

wb = w * cos(p) + h * sin(p)
hb = w * sin(p) + h * cos(p)

wb및 hb이미지로부터 직접 추출 될 수있다. 픽셀 a수를 세어 사각형 의 전체 영역 을 빠르게 추출 할 수도 있습니다 ... 우리는 직사각형을 다루기 때문에 추가 방정식을 얻습니다.

a = w * h

따라서 우리는 3 개의 미지수 ( w, h및 p)를 가진 3 개의 방정식을 가지 는데, 이는 미지수를 결정하기에 충분합니다. 유일한 문제는 방정식에 삼각 함수가 포함되어 있고 적어도 인내와 수학 기술로 시스템을 쉽게 분석 할 수 없다는 것입니다.

내가 구현 한 것은 각도에 대한 무차별 대입이다 p. 일단 p처음 두 방정식은 상기에서 해결 될 수있는 두 개의 선형 방정식의 시스템가 주어진다 w하고 h:

w = (wb * cos(p) - hb * sin(p)) / (cos(p) * cos(p) - sin(p) * sin(p))
h = (hb * cos(p) - wb * sin(p)) / (cos(p) * cos(p) - sin(p) * sin(p))

이 값으로 w * h직사각형의 측정 된 영역과 비교할 수 있습니다 . 두 값은 어느 시점에서 이상적으로 동일합니다. 이것은 물론 부동 소수점 수학에서는 일어나지 않을 것입니다.

w * h각도가 증가함에 따라 값이 감소합니다. 따라서 0.0에서 시작한 다음 처음으로 w * h측정 된 영역보다 작을 때까지 작은 단계 씩 각도를 증가시킵니다 .

코드에는 두 가지 주요 단계 만 있습니다.

  1. 입력에서 경계 상자 및 사각형 영역의 크기를 추출하십시오.
  2. 종료 기준에 도달 할 때까지 후보 각도를 반복합니다.

너비와 높이가 크게 다른 사각형의 경우 출력 정밀도가 좋습니다. 거의 정사각형이고 45도 가까이 회전 한 사각형에서는 다소 문제가 생겨 테스트 예제 2의 7 % 오류 장애물을 거의 제거 할 수 있습니다.

예제 2의 비트 맵은 실제로 약간 이상하게 보입니다. 왼쪽 구석이 의심스럽게 둔해 보입니다. 왼쪽 구석에 하나 이상의 픽셀을 추가하면 둘 다 나아 보이며이 알고리즘의 정밀도가 훨씬 향상됩니다.

답변