Ten fragment kodu rysuje aliasowany biały prostokąt na czarnym tle, podając parametry dotyczące jego wymiarów, położenia, kąta i wymiarów siatki:

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

Reprezentacja tekstu ma miejsce XXwszędzie tam, gdzie na obrazie znajduje się czarny piksel i ..gdziekolwiek jest biały piksel. (Wygląda na spłaszczony, jeśli są Xi ..)

Napisz program, który pobiera tekstową reprezentację prostokąta utworzonego przez Snippet i wyświetla przybliżoną szerokość i wysokość prostokąta, z dokładnością do ± 7% rzeczywistej szerokości i wysokości .

Twój program powinien działać skutecznie dla wszystkich możliwych prostokątów, które mogą zostać narysowane przez fragment kodu, z ograniczeniami, które:

• Szerokość i wysokość prostokąta wynoszą co najmniej 24.
• Szerokość i wysokość siatki wynoszą co najmniej 26.
• Prostokąt nigdy nie dotyka ani nie wychodzi poza granice siatki.

Prostokąt wejściowy może więc mieć dowolny obrót, położenie i wymiary, a siatka może mieć dowolne wymiary, o ile zostaną spełnione trzy powyższe ograniczenia. Pamiętaj, że oprócz wymiarów siatki parametry Snippet mogą być zmiennoprzecinkowe.

Detale

• Weź wejściowy prostokąt tekstu lub weź nazwę pliku zawierającego prostokąt surowy tekst (za pomocą standardowego wejścia lub wiersza poleceń). Możesz założyć, że prostokąt tekstowy ma końcowy znak nowej linii.
• Możesz założyć, że prostokąt tekstowy składa się z dowolnych dwóch różnych znaków drukowalnych ASCII innych niż Xi .jeśli to pożądane. (Newlines muszą pozostać newlines.)
• Wyprowadza zmierzoną szerokość i wysokość jako liczby całkowite lub zmiennoprzecinkowe na standardowe wyjście w dowolnej kolejności (ponieważ nie ma sposobu, aby ustalić, który z nich faktycznie poszedł z którym parametrem). Dowolny format, który wyraźnie pokazuje dwa wymiary jest w porządku, na przykład D1 D2, D1,D2, D1\nD2, (D1, D2), itd.
• Zamiast programu możesz napisać funkcję, która pobiera prostokąt tekstowy jako ciąg lub nazwę pliku i drukuje wynik normalnie lub zwraca jako ciąg lub listę / krotkę z dwoma elementami.
• Pamiętaj, że XXlub ..to jeden „piksel” prostokąta, a nie dwa.

Przykłady

Dawny. 1

Parametry: grid w:60 grid h:34 w:40 h:24 x:0 y:0 θ:12(wartości domyślne fragmentu kodu)

Wejście

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

Przykładowe wyniki

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

Dawny. 2)

Parametry: grid w:55 grid h:40 w:24.5 h:24 x:-10.1 y:2 θ:38.5

Wejście

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

Przykładowe wyniki

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

Punktacja

Najkrótszy kod w bajtach wygrywa. Tiebreaker to najwyżej oceniany post.

Matlab, 226 bajtów

Pomysł jest prosty: najpierw próbuję dowiedzieć się, o ile obrócony został prostokąt, a następnie odpowiednio obrócić obraz, aby prostokąt był ustawiony pionowo. Następnie po prostu „sumuję” wszystkie piksele w kolumnach wierszy i próbuję policzyć, ile sum jest powyżej średniej (proste progi) w celu ustalenia szerokości i wysokości. Ta prosta metoda działa zaskakująco niezawodnie.

Jak mogę wykryć kąt?

Po prostu próbuję każdego kroku (jeden stopień) i sumuję wzdłuż kolumn i otrzymuję wektor sum. Gdy prostokąt jest ustawiony pionowo, idealnie powinienem uzyskać tylko dwie nagłe zmiany w tym wektorze sum. Jeśli kwadrat znajduje się na czubku, zmiany są bardzo stopniowe. Więc po prostu używam pierwszej pochodnej i staram się zminimalizować liczbę „skoków”. Tutaj możesz zobaczyć wykres kryterium, które staramy się zminimalizować. Zauważ, że możesz zobaczyć cztery minima, które odpowiadają czterem możliwym orientacjom pionowym.

Dalsze przemyślenia: Nie jestem pewien, jak bardzo można by grać w golfa, ponieważ ekshibicjonalne wyszukiwanie kąta zajmuje wiele znaków i wątpię, czy można to tak dobrze osiągnąć dzięki wbudowanym metodom optymalizacji, ponieważ, jak widać, istnieje wiele lokalnych minimów którego nie szukamy. Można łatwo poprawić dokładność (na dużych zdjęciach), wybierając mniejszy rozmiar krok do kąta i tylko szukać 90 ° zamiast 360 °, więc można wymienić 0:360się 0:.1:90lub somehting tak. Ale w każdym razie dla mnie wyzwaniem było raczej znalezienie solidnego algorytmu zamiast gry w golfa i jestem pewien, że wpisy języków golfowych pozostawią moje zgłoszenie daleko w tyle =)

PS: Ktoś naprawdę powinien czerpać język golfa z Matlab / Octave.

Wyjścia

Przykład 1:

 25    39

Przykład 2:

 25    24

Kod

Gra w golfa:

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

Nie golfowany:

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 bajtów

To może być grałem trochę więcej ..

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

Jak to działa

Logika jest dość prosta, jeśli się nad tym zastanowić.

Wszystko, czego potrzebujemy od X.kombinacji wejściowych, to 3 współrzędne dwóch sąsiednich stron. Oto jak je otrzymujemy:

First

W dowolnej orientacji prostokąta pierwszy .w całym wejściu będzie jednym z rogów. Na przykład..

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

Tu, pierwszy .znajduje się w 2 ^nd linii, 8 ^th kolumn.

Ale to nie wszystko, musimy dokonać korekty i dodać szerokość .przebiegu w tej linii do współrzędnych, aby uzyskać współrzędne prawego końca.

Second

Jeśli transponujemy powyższy prostokąt (obrócony na nowych liniach), wówczas lewy dolny róg zajmuje miejsce powyższego kroku. Ale tutaj nie kompensujemy .długości przebiegu, ponieważ i tak chcielibyśmy uzyskać lewą dolną współrzędną krawędzi (która w formie transponowanej nadal będzie pierwszą napotkaną .)

Rest two

W przypadku pozostałych dwóch współrzędnych po prostu odwracamy prostokąt w poziomie i wykonujemy powyższe dwa kroki. Jeden z rogów będzie wspólny od pierwszych dwóch.

Po uzyskaniu wszystkich 4, po prostu wykonujemy prostą matematykę, aby uzyskać odległości.

Teraz nie jest to najdokładniejsza metoda, ale działa dobrze w granicach błędu i dobrze dla wszystkich możliwych orientacji prostokąta.

Rozszerzenie kodu (nieco nieaktualne)

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

Wypróbuj online tutaj

Python 3, 347 337 bajtów

Okazało się to trudniejsze niż się spodziewałem. Praca w toku...

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

Definiuje funkcję, która fprzyjmuje ciąg jako argument i wypisuje wynik do STDOUT.

Pyth, 87 84 82 81 75 72 71 bajtów

(MOŻLIWE NIEPRAWIDŁOWE, DOCHODZENIE KIEDY Wrócę do domu)

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

O wiele za długo. Zasadniczo port poprzedniego. Odległość .aeuklidesowa kochającego Pytha . Pobiera dane wejściowe przez STDIN i podaje dane wyjściowe przez STDOUT. Oczekuje, że znak niebędący prostokątem będzie pisany małymi literami x(cóż, wszystko o wartości ASCII 98 lub większej).

Algorytm

Oba wykorzystują ten sam algorytm. Zasadniczo zaczynam od tablicy zawierającej środek masy obszaru prostokąta. Następnie dodaję trzy punkty do tablicy wszystkich punktów w prostokącie, zawsze wybierając ten z maksymalną sumą odległości do punktów znajdujących się już w tablicy. Wynik to zawsze trzy punkty w różnych rogach prostokąta. Następnie po prostu obliczam wszystkie trzy odległości między tymi trzema punktami i biorę dwa najkrótsze.

Python 2, 342 bajty

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

Inspiracją jest algorytm @ Pietu1998. Przyjmuje pomysł określenia jednego rogu jako punktu najdalej od centrum, ale różni się od tego:

• Drugi narożnik określam jako punkt o największym iloczynie krzyżowym z wektorem od środka do pierwszego narożnika. Daje to punkt o największej odległości od linii od środka do pierwszego rogu.
• Nie ma potrzeby szukania trzeciego rogu, ponieważ jest to lustrzane odbicie drugiego rogu względem środka.

Zatem kod ma następującą sekwencję:

• Pierwsza pętla znajduje się nad liniami na wejściu i tworzy listę rpunktów prostokątnych.
• Druga pętla oblicza średnią wszystkich punktów prostokąta, podając środek prostokąta.
• Trzecia pętla znajduje punkt najdalej od centrum. To jest pierwszy róg. Jednocześnie odejmuje środek od punktów na liście, aby współrzędne punktu były względne względem środka dla pozostałego obliczenia.
• Czwarta pętla znajduje punkt o największym iloczynie krzyżowym z wektorem do pierwszego rogu. To jest drugi róg.
• Drukuje odległość między pierwszym rogiem a drugim rogiem oraz odległość między pierwszym rogiem a lustrzanym odbiciem drugiego rogu.
• 1.0jest dodawany do odległości, ponieważ pierwotne obliczenia odległości wykorzystują wskaźniki pikseli. Na przykład, jeśli masz 5 pikseli, różnica między indeksem ostatniego i pierwszego piksela wynosiła tylko 4, co wymaga kompensacji w wyniku końcowym.

Precyzja jest całkiem dobra. Dla dwóch przykładów:

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

Python 2, 272 bajty

Opublikowanie tego jako osobnej odpowiedzi, ponieważ jest to zupełnie inny algorytm niż mój poprzedni:

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

Takie podejście w ogóle nie identyfikuje zakrętów. Opiera się na spostrzeżeniu, że rozmiar (szerokość i wysokość) obwiedni i obszar obróconego prostokąta są wystarczające do określenia szerokości i wysokości prostokąta.

Jeśli spojrzysz na szkic, dość łatwo jest obliczyć szerokość ( wb) i wysokość ( hb) obwiedni za pomocą w/ hrozmiaru prostokąta i pkąta obrotu:

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

wbi hbmożna je wyodrębnić bezpośrednio z obrazu. Możemy również szybko wyodrębnić całkowitą powierzchnię aprostokąta, zliczając liczbę ..pikseli. Ponieważ mamy do czynienia z prostokątem, daje nam to dodatkowe równanie:

a = w * h

Więc mamy 3 równań z 3 niewiadomymi ( w, hi p), która wystarcza do określenia niewiadomych. Jedynym problemem jest to, że równania zawierają funkcje trygonometryczne, a przynajmniej przy mojej cierpliwości i umiejętnościach matematycznych systemu nie da się łatwo rozwiązać analitycznie.

Zaimplementowałem brutalne poszukiwanie kąta p. Po ppodaniu pierwsze dwa powyższe równania stają się układem dwóch równań liniowych, które można rozwiązać wi 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))

Dzięki tym wartościom możemy następnie porównać w * hze zmierzonym obszarem prostokąta. Dwie wartości idealnie byłyby w pewnym momencie równe. Nie stanie się to oczywiście w matematyce zmiennoprzecinkowej.

Wartość w * hmaleje wraz ze wzrostem kąta. Zaczynamy więc od kąta 0,0, a następnie zwiększamy kąt małymi krokami, aż po raz pierwszy w * hbędzie mniejszy niż zmierzony obszar.

Kod ma tylko dwa główne kroki:

1. Wyodrębnij wielkość ramki granicznej i obszaru prostokąta z danych wejściowych.
2. Pętla nad kątami kandydującymi do momentu spełnienia kryterium zakończenia.

Dokładność wydruku jest dobra dla prostokątów, w których szerokość i wysokość są znacząco różne. Robi się nieco niepewnie z prostokątami, które są prawie kwadratowe i obrócone o prawie 45 stopni, ledwo usuwając przeszkodę błędu 7% dla przykładu testowego 2.

Bitmapa na przykład 2 wygląda nieco dziwnie. Lewy róg wygląda podejrzanie nudno. Jeśli dodam jeszcze jeden piksel w lewym rogu, oba wyglądają lepiej (dla mnie) i dają znacznie lepszą precyzję dla tego algorytmu.