kasprus Temat założony przez niniejszego użytkownika |
Prostokąty - proszę o pomoc!!! » 2011-05-16 17:50:25 Witam,
mam mały problem. Mam napisać funkcję, która sprawdzi, czy prostokąty o bokach równoległych do osi w układzie współrzędnym nachodzą na siebie. Uznajemy, że jeżeli stykają się kawałkiem boku, to też nachodzą, ale jeżeli tylko wierzchołkiem, to nie nachodzą. Funkcja ta ma być elementem programu. Niestety, nie wiem, czy napisałem ją poprawnie, a bez tego pisanie programu ni ma sensu. Prosiłbym o sprawdzenie i ewentualne poprawienie kodu:
#include<iostream> using namespace std; struct prostokat { int x1; int y1; int x2; int y2; }; prostokat tab[ 10001 ]; inline bool czy_nachodzi( prostokat a, prostokat b ) { if( b.x1 < a.x1 ) return czy_nachodzi( b, a ); if( a.x2 >= b.x1 ) { if( b.y2 >= a.y1 && a.y2 >= b.y1 ) { if( a.x2 == b.x1 && b.y2 == a.y1 || a.x2 == b.x1 && a.y2 == b.y1 ) return false; return true; } } return false; } int main() { prostokat a, b; cin >> a.x1 >> a.y1 >> a.x2 >> a.y2 >> b.x1 >> b.y1 >> b.x2 >> b.y2; cout << czy_nachodzi( a, b ); system( "pause" ); return 0; }
|
|
DejaVu |
» 2011-05-16 18:10:47 A co to za problem napisać sobie przypadki testowe? :) |
|
kasprus Temat założony przez niniejszego użytkownika |
» 2011-05-16 18:16:44 Chodzi o to, że nie wiem, czy rozważam wszystkie przypadki testowe. |
|
Mrowqa |
» 2011-05-16 18:16:46 W większych algorytmach ( choć to na razie jest jeszcze mały :P ) rób tak jak to kolega wyżej powiedział :P Ja jak robiłem algorytmy szyfrujące to dowiedziałem się o kilku ciekawych i dziwnych rzeczach ( nie których do tej pory nie rozumiem ;P - grunt, że znalazłem rozwiązanie i działa :D ).
EDIT: nie zauważyłem posta wyżej :P Spróbuj wykorzystać ten algorytm na wszystkie przypadki :P tzn zrób kilka testów uwzględniając wszystkie przypadki :D
Pozdrawiam, Mrowqa |
|
kasprus Temat założony przez niniejszego użytkownika |
» 2011-05-16 18:23:01 No i niestety znalazłem błąd. Dla przykładu: 0 10 5 0
0 8 5 0 odpowiedź jest zła. Jak to mogę poprawić? |
|
DejaVu |
» 2011-05-16 18:26:21 Prostokąt powinien zawsze mieć x1<=x2 oraz y1<=y2. Twój przypadek testowy łamie tą zasadę. |
|
Mrowqa |
» 2011-05-16 18:27:59 Na razie nie mam czasu, ale z tego co "na szybkiego" zobaczyłem, to coś mi się zdaję, że jeśli funkcja wywołuję sama siebie ( rekurencja bezpośrednia ) to nie może być inline :P ( z resztą to samo z siebie nie ma sensu :P )
Pozdrawiam, Mrowqa |
|
absflg |
» 2011-05-16 18:57:14 Zwykle kolizje się sprawdza hurtem, więc lepiej by było tak:
inline bool czy_nachodzi( prostokat a, prostokat b ) { return !( b.y2 < a.y1 || a.y2 < b.y1 || b.x2 < a.x1 || a.x2 < b.x1 ); }
Im mniej wyliczania, tym lepiej. Jeżeli ma traktować pokrywanie się krawędzi jako brak kolizji to zmień operatory < na <=. |
|
« 1 » |