6441. Prostokąty

Dlaczego odnosisz się do postu który skasowałem a nie do tego ostatniego? Jakim cudem w ogóle jesteś w stanie czytać skasowany post? Uważasz że to jest tak trywialne że w gimnazjum można to rozwiązać pitagorasem? Ciekawe że sztab matematyków na całym świecie się nad tym głowi latami.

Każdy jest w stanie. Wystarczy kliknąć w historię edycji. Przy okazji odpowiednimi kolorami i przekreśleniem zaznaczone jest to co było usunięte, np. usunięto: “Przepraszam bardzo ale może ktoś napisałby nową treść do tego zadania bo (…)”. Taki diff.

PS dla młodszych
Dlatego uważamy co piszemy w sieci bo przecież nie jesteśmy anonimowi

A potem wystarczy już tylko twierdzenie Pitagorasa, podobieństwo trójkątów, linijka …

Nie, nie uważam i nic takiego nie napisałem.

Zdaje się to wszystko jest w gimnazjum…

Nigdy nie byłem w gimnazjum, więc nie wiem. W “moich” czasach nie było. Nie jestem matematykiem, ale to nie znaczy, że jestem humanistą, ale wykształcenia informatycznego też nie mam. Co do wzoru. Matematycy zajmują sie udowadnianiem, a nie tylko wyprowadzeniem wzoru. Ja zadowoliłem się tylko wyprowadzeniem, a dowodem poprawności było AC na SPOJ’u. I nie było to ot takie sobie wzięcie ołówka i papieru i wyprowadzenie potrzebnego wzoru i za pierwszym razem. Było też wcześniej dużo myślenia, kombinowania, poprawiania, rysowania. Między moim pierwszym WA, a pierwszym AC, na mojej liście zgłoszeń do tego zadania jest dużo więcej odstępu czasowego niż jeden dzień, czy tydzień. Jest kilka miesięcy.
Otrzymanie wzoru, to nie jakieś banalne i trywialne wykorzystanie twierdzenia Pitagorasa, a także podobieństwa trójkątów. To ułożenie równania, czy układu równań, a potem odpowiednie ich przekształcenie.

Istnieją podobne strony do spoja gdzie mierzony jest nie czas wykonania programu (tzn. to też), ale przede wszystkim jego złożoność. Na spoju też mnie często irytuje to, że napiszę coś w Pythonie i “przekroczono limit czasu” - przerzucę algorytm na C++ i nagle wynik się mieści lub nawet jest jednym z lepszych. To też chcąc być wysoko w rankingu spoj narzuca języki oparte na C i koniec (również niektórymi zadaniami, które są zatrzeżone dla C\C++) i nie idzie się tutaj uczyć innego języka.
Taki mój prywatny osąd. Mi to nie przeszkadza (już), ale rozumiem.

Lubię spoja bo jest po polsku. Za moich czasów jedynym słusznym językiem w szkole był rosyjski Wolę teraz poświęcić czas na programowanie niż na zrozumienie treści po angielsku Poza tym jak wypełniałem konto na jakimś innym portalu tego typu to w rubryce gender miałem do wyboru male, female i others… To podziękowałem

Od 5 lat próbuję uzyskać wynik pozytywny… bez skutku…
Próby: pola ✓, obwodu ✓, średnicy ✓, grubości ✓.
Dopasowania pod kątem prostym… Nic nie wchodzi.
Machnąłem nawet ten magiczny wzorek z książki.
Dzięki niemu wchodzą testy {100, 50, 105, 9} i {81, 59, 88, 13}.

Wklepałem dodatkowo test z forum https://matematyka.pl/206549.htm11 :
if ( (double)b/a < (double)d/c ) __NIE__;

Wyprowadziłem nawet wzór na test obrotu pod danym kątem:

// part of solution from the past
double _c, _d, alfa;
alfa = atan2(b, a);
_c = c * sin(alfa) + d * cos(alfa);
_d = c * cos(alfa) + d * sin(alfa);
if( (a > _c && b > _d) ||
    (a > _d && b > _c) ) __TAK__;

Ciągle otrzymuję WA i mam wrażenie, że to
zadanie jest zepsute przez przypadki autora.

@narbej a miałem już sprawdzić czego mi brakuje z tego kodu…

@rashmistrz wstaw cały kod. Sposób opisany w linku jest poprawny i zadanie raczej nie jest zepsute.

#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;

#define __TAK__ { cout << "TAK\n"; continue; }
#define __NIE__ { cout << "NIE\n"; continue; }
#define __UND__ { cout << "UND\n"; continue; }

int main()
{
    int problems;
    cin >> problems;
    
    while ( problems-- )
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;

        // normalisation
        if ( a < b ) swap( a, b );
        if ( c < d ) swap( c, d );
        
        // basic tests
        if ( d < b )            __NIE__;
        if ( a == c || b == d ) __NIE__;
        if ( a > c && b > d )   __TAK__;
        if ( a + b < c + d )    __NIE__;
        if ( a * b < c * d )    __NIE__;
        
        // advanced tests
        if ( hypot( a, b ) < hypot( c, d ) )    __NIE__;
        if ( (double)b/a < (double)d/c     )    __NIE__;
        
        // part of solution from the past
        double _c, _d, alfa;
        alfa = atan2(b, a);
        _c = c * sin(alfa) + d * cos(alfa);
        _d = c * cos(alfa) + d * sin(alfa);
        if( (a > _c && b > _d) ||
            (a > _d && b > _c) ) __TAK__;

        // mysterious formula from book
        {
            double x;
            x = 2 * a;
            x *= c * d;
            x /= ( c*c + d*d );

            double x_;
            x_  = ( c*c - d*d );
            x_ *= sqrt( c*c - a*a + d*d );
            x_ /= ( c*c + d*d );

            x += x_;
            if ( c > a && b > x ) __TAK__ else __NIE__;
        }
    }
}

Z tamtego forum w rozwiązaniu od Satireva
nie rozumiem dlaczego akurat B porównuje
z przyprostokątną mniejszego,
dalej nie przyglądałem się jego rozwiązaniu.

testy (wg mnie) są poprawne, dawno temu zadanie rozwiązałem, wzory wyprowadziłem sam
zaliczyłem w pierwszej próbie po wyprowadzeniu wzorów na położenie ukośne (bo przedtem miałem wiele prób ułożeń równoległych - ale się nie sprawdziły )

wzór, który wyprowadziłem jest inny, niż podany w linku (link pojawił się dużo później) - czy jest równoważny - nigdy nie chciało mi się sprawdzić, tym bardziej, że nie mam notatek, jak go wyprowadziłem a jedynie postać końcową

wyprowadzenie wzoru nie zajęło mi więcej niż 2-3 godziny (bo gdyby było to dłużej, to bym zrezygnował )
nie jest to też pewnie zbyt trudne - wzór Pitagorasa + wzory skróconego mnożenia + dużo uwagi

@hipcia https://ideone.com/iofhwD4

7 10 3  5 - 27TAK
3  6 4  2 - 27TAK
4 10 9  1 - 27TAK
8 10 2 10 - 26NIE

Wszystko wygląda dobrze.
Nie wiem dlaczego test na grubość nie działa :F

EDIT: (nierozwiązujący problemu)
Źle wyprowadziłem z: min{ c, d } <= min{ a, b }:
Powinno być d >= b zamiast b > d dla NIE.

EDIT2:
Złączyłem w jedno uzyskując:
if ( a == c || b <= d ) __NIE__;

EDIT3: https://ideone.com/vLPkim6

EDIT4: ideone com XzVWIg
Trochę ślepy byłem z tym testem:
8 10 2 10 - powinno być TAK

Jednakże nadal WA, a pomysłów do zaimplementowania, brak.
Mogę spróbować z poszukiwaniem przybliżenia pod jakim kątem ma być ustawione.
Jeśli da się zmieścić prostokąt w pierwszym to powinien istnieć taki kąt pod którym po obróceniu,
jego rzuty proste powinny się mieścić na bokach większego. W dobrą stronę idę?

Mam prośbę. Mógłby ktoś udostępnić odpowiedzi “poprawnego” programu na te testy?:

21
3 1 1 2
3 3 1 3
3 3 1 4
4 5 6 1
6 1 2 3
8 6 9 1
8 10 2 8
8 8 10 10
10 10 8 8
9 9 10 1
9 6 10 1
10 10 10 10
47 32 48 13
81 59 88 13
80 79 105 7
91 77 95 25
100 50 9 105
151 122 170 25
200 171 205 60
1233 1234 1235 509
1234 1234 1234 511

Moje odpowiedzi to: (włączając wpisane i styczne)

NIE TAK NIE NIE NIE
TAK TAK NIE TAK TAK
NIE NIE NIE TAK TAK
NIE TAK NIE NIE TAK
TAK

Gdyby ktoś jeszcze potrzebował to to są testy które zawsze mają zwracać NIE:

70
178 99 179 33
140 121 147 39
149 130 178 20
209 157 218 47
229 159 255 26
180 161 200 42
239 162 240 57
196 165 223 34
281 165 283 55
337 177 347 45
219 190 238 53
210 194 261 25
356 198 358 66
242 201 253 64
215 206 219 79
289 209 298 65
336 216 372 31
298 218 310 65
308 220 331 52
335 222 362 45
242 223 244 86
238 224 276 51
357 224 386 41
263 225 301 46
320 225 322 79
338 228 347 70
267 229 276 78
318 230 330 69
254 231 276 68
306 235 324 66
346 238 374 51
339 239 370 49
253 240 271 78
285 240 318 56
280 242 294 78
279 245 291 82
257 246 269 87
343 246 369 58
346 248 370 61
298 253 318 75
277 254 279 98
302 255 358 38
367 256 376 81
373 257 382 81
285 260 290 97
298 260 356 40
348 260 355 87
341 262 346 91
274 269 313 71
283 274 316 78
290 274 382 17
320 274 331 93
324 275 375 51
370 279 384 86
324 280 349 81
326 287 327 110
307 298 318 110
313 299 362 71
353 299 379 86
335 302 366 86
323 307 340 106
310 308 336 101
326 308 339 110
345 312 382 84
355 315 384 92
362 319 370 115
373 319 386 108
352 320 368 109
331 328 359 107
366 337 367 132

Mam już te zadanie serdecznie gdzieś.
Napisałem też program, który siłowo uzyskuje rozwiązanie dla pochylenia:
–SNAP!– (W odpowiedziach poniżej jest finalna wersja z większą precyzją.)

Mój wynik:

NIE TAK NIE NIE NIE
TAK TAK NIE TAK TAK 
NIE NIE NIE TAK TAK 
NIE TAK NIE **TAK** TAK
TAK

Czyli problem leży tutaj:

200 171 205 60

EDIT: Kilka dodatkowych testów - wszystkie na TAK:

3
73 88 95 20
82 65 10 95
56 70 10 80

Wyklepałem nowy znajdowacz kątów o ogromnej precyzji:

#include <cmath>
#include <cfloat>
#include <limits>
#include <iostream>
#include <algorithm>
using namespace std;

#define __TAK__ { cout /*<< __LINE__*/ << "TAK\n"; return 0; }
#define __NIE__ { cout /*<< __LINE__*/ << "NIE\n"; return 0; }
#define __EPS__ { cout /*<< __LINE__*/ << "EPS\n"; return 1; }

int main()
{
    int a, b, c, d;
    long double _c, _d, alfa, beta;
    cin >> a >> b >> c >> d;
    
    if (a < b) swap(a, b);  // a >= b
    if (c < d) swap(c, d);  // c >= d

    if ( d >  b ) __NIE__   // thickness
    if ( a >= c ) __TAK__   // fit check
    if ( c == d ) __NIE__   // square cXd

    alfa = atan2(b, a);     // y, x
    beta = atan2(d, c);     // y, x
    _c = c * cos(alfa) + d * sin(alfa);
    _d = c * sin(alfa) + d * cos(alfa);

    if ( a >  _c && b >  _d )   __TAK__
    if ( a <= _c && b <= _d )   __NIE__
    if ( beta > alfa )          __NIE__

    int step = 1;
    bool cross = false;
    long double eps = LDBL_EPSILON;
    long double lower = abs( alfa - beta ); 
    long double upper = alfa;
    enum{ EPS, TAK, NIE } answer;

    do{
        if (a < _c && b < _d) { answer = NIE; break; }
        if (a > _c && b > _d) { answer = TAK; break; }
        if (beta < eps)       { answer = EPS; break; }

        _c > a ? lower = alfa : upper = alfa;
        if ( cross != (_c > a) ) beta = (upper - lower) / 2;
        ( cross = _c > a ) ? alfa += beta : alfa -= beta;

        _c = c * cos(alfa) + d * sin(alfa);
        _d = c * sin(alfa) + d * cos(alfa);
    } while ( step++ ); 
    
    switch( answer )
    {
        case NIE: cout << "NIE"; break;
        case TAK: cout << "TAK"; break;
        case EPS: cout << "EPS"; break;
    }
    
    cout.precision(16);
    cout << '\t'<< step << '\t' << alfa << '\t' << beta << '\n'; 
    cout << _c << '\t' << _d << '\t' << (a - _c)  << '\t' << (b - _d) << '\n';
    
    if( answer == EPS && (!((a - _c) + (b - _d)) || !(a - _c) || !(b - _d) ) )
        cout << "Warning!\t           ---- Oscillation! ----            \n";
}

Wygląda na to, że autor zadania pomylił się w treści lub testach,
mówiąc że ma się zmieścić “nie dotykając jego krawędzi”…
Przedstawione w testach przypadki są wpisywalne…
Te testy według mnie powinny zwracać wyłącznie NIE:

6
56 70 10 80
73 88 95 20
82 65 10 95
91 77 95 25
151 122 170 25
171 200 205 60

Wygląda na to że te przypadki generują takie coś:

56 70 10 80
EPS     95      0.6435011087932844      5.421010862427522e-20
70      56      0       3.469446951953614e-18
Warning!                   ---- Oscillation! ----

73 88 95 20
EPS     94      0.6435011087932844      8.131516293641283e-20
88      73      -6.938893903907228e-18  6.938893903907228e-18
Warning!                   ---- Oscillation! ----

82 65 10 95
EPS     96      0.6435011087932844      5.421010862427522e-20
82      65      0       0
Warning!                   ---- Oscillation! ----

91 77 95 25
EPS     101     0.6435011087932844      5.421010862427522e-20
91      77      0       0
Warning!                   ---- Oscillation! ----

151 122 170 25
EPS     93      0.6435011087932844      5.421010862427522e-20
151     122     0       6.938893903907228e-18
Warning!                   ---- Oscillation! ----

171 200 205 60
EPS     99      0.6435011087932844      5.421010862427522e-20
200     171     -2.775557561562891e-17  2.775557561562891e-17
Warning!                   ---- Oscillation! ----

Próby dopasowania nie dość że rozbijają się o epsilon,
to i jeszcze c′ i d′ są praktycznie równe bokom a i b…
Co ciekawsze, ich częścią wspólną jest kąt ~36.87°.
Proszę, wyprowadźcie mnie z możliwego błędu.

Dla tych z przyszłości którzy również mają problem z tym zadaniem.

W testach autora znajdują się fałszywe pozytywy z powodu
problemów z precyzją liczb zmiennoprzecinkowych
i tego w jaki został wytworzony zestaw testowy…

Trzeba kombinować z różnymi wzorami
i szerokością zmiennych żeby wstrzelić się w klucz.

Uzyskałem AC przy odpowiedziach
NIE TAK NIE NIE NIE TAK
dla poniższego zestawu testów:

6
56 70 10 80
73 88 95 20
82 65 10 95
91 77 95 25
151 122 170 25
171 200 205 60

@hipcia
Dla zestawu testowego od Ciebie
mam TAK NIE NIE jakimiś cudem

Ja z moim kodem AC dostaję:

TAK NIE NIE NIE NIE TAK

Więc wygląda na to, że chyba ja czegoś nie uwzględniłem, a autor po prostu nie dał takich testów