Pitagorasz

Ma ezt a feladatot dolgozzuk fel:

http://www.spoj.com/problems/EQBOX/

Bejön négy szám: A, B, C, D. Egészek. 1 és 50.000 közt.

Kérdés: befér-e egy A*B-s téglalapba egy C*D-s téglalap a határai érintése nélkül?

Ilyen tesztesetből jön be kb 10.000.

Első érzésből az ember azt hiszi, hogy megvan a könnyű feladat, adja a kódernek, hasonlítsa össze a kisebbet a kisebbel, a nagyobbat a nagyobbal és ha a C*D-snek a rövidebb oldala rövidebb, mint az A*B-sek, és a hosszabb is, akkor true, egyébként false.

WA

OK, akkor olvassuk el még egyszer. LEHET FORGATNI.

Így már egész más a leányzó fekvése.. egy 8x8-as boxba pl befér egy 10x2-es, ha 45 fokban elforgatva rakjuk bele.

A forgatással kapcsolatban: ha tetszőleges szögű forgatással kell dolgoznunk, akkor rossz esetben szögfüggvényezni, kevésbé rossz esetben gyököt vonni kell. Mindkét esetben át kell menni lebegőpontba, amivel az a baj, hogy a számítások pontossága is elronthatja a napunkat, nullára sose tesztelhetünk (helyette mindig azt kell nézni, hogy egy érték +- epszilon közt van-e, ahol epszilon valami pici konstans. Meg persze a float kulcsszót felejtsük el, sose ismertük, minden double.

És még az is hozzájön, hogy a sqrt, sin, stb függvények (az egész aritmetikához képest) nagyon lassúak. Emiatt minél kevesebb olyan esetet kellene hagyjunk, amikor ténylegesen átmegyünk lebegőpontba, és amit egész aritmetikával meg lehet oldani (mivel az input egész, erre van esélyünk), azt egésszel oldjuk meg, még ha több is lesz benne az if.

Először is rendezzük le az oldalakat A <= B, C <= D sorrendbe, úgy könnyebb lesz kezelni a továbbiakat, és kevesebb lesz az if, nem spagettit készítünk, hanem kódot.

Aztán, nyilván ha C < A és D < B, akkor nyilván befér, ezt az esetet gyorsan lekezeljük. (ezt amúgy is megcsináltuk az előző WA-s beküldésnél, akkor meg miért töröljük ki :D )

Lássuk a forgatást: ha a C*D-s téglalapot forgatjuk, akkor közben C-nél rövidebb nem lesz egyik tengelyirányba se. (Már négyzetre se lehet kisebb, és mivel D legalább C, ettől alacsonyabbá nem válhat.)

Emiatt ha A <= C, nem fog beférni.

Aztán az is tiszta, hogy ha befér, akkor az átlója is befér. Az A*B-s téglalap két legtávolabbi pontja szintén az átlója. Vagyis ha a C*D-s téglalap átlója hosszabb, nem fog beférni. Pitagorasz. Gyököt nyilván nem vonunk:

Ha A*A + B*B <= C*C + D*D, nem fog beférni.

Na most már (szerintem) viszont kell legalább gyökvonás is. 

Kép:

Gondolatban megdupláztam az a,b,c,d értékeket. A fekete téglalap az A*B téglalap bal felső negyede. Ha befér, szimmetriai okokból befér úgy is, ha a két téglalap középpontja egybeesik. Annyit kell kiszámolnunk, hogy a C*D téglalap átlója (a képen a piros vonalak) hol "ütközne bele" a bal oldali ill. felső oldalba. Ha a két ütközési pont közé legalább a C*D téglalap rövidebb oldala befér (kék vonal > C), akkor befér: csak megfelelően összébb kell csukni az átlókat, a hosszabb oldal szimmetria és konvexitás miatt  be fog férni automatikusan.

Pitagorasz: a piros hossza gyök(c*c+d*d), akkor x=gyök(c*c+d*d-a*a) és y=gyök(c*c+d*d-b*b). A kék vonal egy átfogó, a befogók a-x és b-y, ezekből számítva kék=gyök((a-x)*(a-x)+(b-y)*(b-y)). Ha kék > C, befér, különben nem.

Kód: http://pastebin.com/HYAH2cvs, 0:04, jó ez így. Lehet, hogy még ki lehet belőle küszöbölni a gyökvonásokat pár iffel, vagy benéztem valamit és egész aritmetikával is megoldható? Vagy már megint a scanf tart sokba? :-)

Bottom line: tartsunk egész aritmetikát, amíg csak lehet, ha meg nem lehet, double, és minél kevesebb bonyolult lebegőpontos művelet, az se a pontosságnak, se a futásidőnek nem tesz jót.