[C++] Punkt przecięcia dwóch odcinków


(Kdryja) #1

Mam napisać program, który na wejściu dostaje N oznaczające ilość testów i w kolejnych N - wierszach X1 Y1 X2 Y2 X3 Y3 X4 Y4 oznaczające kolejno współrzędne początku i końca pierwszego odcinka oraz współrzędne początku i końca drugiego odcinka na układzie współrzędnych, a na wyjściu współrzędne punktu przecięcia tych odcinków, z dokładnością do dwóch miejsc po przecinku.. Jeżeli nie ma takiego albo jest ich więcej niż jeden, program ma wypisać NIE.

Napisałem coś takiego. Nie wiedzieć czemu przechodzi tylko przykładowy test, a na reszcie pokazuje błąd. Może wy znajdziecie co jest nie tak?

#include

#include

using namespace std;

int main()

{

    double x1,y1,x2,y2,x3,y3,x4,y4,x,y;

    int n;

    double a1,b1,a2,b2;

    cin>>n;

    for(int i=0;i
    {

            cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;

            a1=(y1-y2)/(x1-x2);

            b1=y1-(x1*((y1-y2)/(x1-x2)));

            a2=(y3-y4)/(x3-x4);

            b2=y3-(x3*((y3-y4)/(x3-x4)));

            if(b1==b2) cout<<"NIE"<
            else

            {

                x=(b2-b1)/(a1-a2);

                y=(a1*x)+b1;

                cout<
            }


    }            

    return 0;  

}

Z góry dzięki Wam za pomoc.


(etam) #2

Porównywanie typów float i double operatorem == prawie zawsze da nie taki wynik jakiego się spodziewasz. Zaokrąglenia są bezlitosne. Spróbuj wymyślić jak dać odpowiedź “NIE” porównując ze sobą dane współrzędne.


([alex]) #3

skrzyżowanie (prostej przez A,B) z (prostą przez C,D):

x=((Bx-Ax)*(Dx*Cy-Dy*Cx)-(Dx-Cx)*(Bx*Ay-By*Ax))/((By-Ay)*(Dx-Cx)-(Dy-Cy)*(Bx-Ax));

y=((Dy-Cy)*(Bx*Ay-By*Ax)-(By-Ay)*(Dx*Cy-Dy*Cx))/((Dy-Cy)*(Bx-Ax)-(By-Ay)*(Dx-Cx));

(stasinek) #4

a sprawdzasz dzielenie przez zero? :stuck_out_tongue:

Twój wzór jest poprawny ale jeszcze troche brakuje do ostatecznej odpowiedzi, możesz podstawić wzory a i b bezpośrednio do równania x i y jak to zrobił alex, możesz użyć #define a1 blabla żeby sobie to uprościć wizualnie zamiast stosować pośrednie zmienne w których traci się kapke informacji bo i tak ostateczną odpowiedź uzyskasz sprawdzając czy x i y z wyliczonych przez alexa wzorów mieści się w przedziałach x1-x2,x3-x4, y1-y2,y3-y4

jeśli przekształcisz wzory a, b i x y wyjdzie Ci po przekształceniu(wspólnych mianowników) jedno dzielenie zamiast trzech,

sporo mnożeń (x1-x2)(x3-x4) - wspólny mianownik - tak jak to zrobił alex

jak podstawisz po przekształceniach do y wyjdzie sporo mnożeń, jedno duże dzielenie z dodawaniem, skoro żeby sprawdzić odpowiedź dla odcinków trzeba będzie x i y porównać z zakresami x > x1 && x< x2 && y > y1 && y > y2(analogicznie dla drugiego wszstko &&) zobaczysz że wszystkie te x1, x2, y1, y2 wystarczyło by pomnożyć przez mianowniki z wzoru x i y i porównywałbyś troszke inne liczby z innymi większymi liczbami ale bez dzieleń, wówczas zniknie problem double, skoro zniknie dzielenie to można użyć liczb stałoprzecinkowych, zobaczysz że…DZIELENIE to ZŁO trzeba go unikać jak ognia i jeśli jest możliwość używać mnożenia

nie bez kozery we wszelkich SIMDach w procesorach jedne z najważniejszych operacji to mnożenia z dodawaniem liczb w sytuacjach zbliżonych do Twojej lub np. mnożenia macierzy

PS dobrze kombinujesz, w sumie wcześniej nie wiedziałem że problem wcale nie jest taki prosty jak mógłby się wydawać, ciekaw jestem ostatecznej postaci :wink:

PS jak ogarniesz i stworzysz funkcje można by napisać ciekawy bajer z jej wykorzystaniem

coś co rysuje odcinki w kierunkach wyznaczonych przez odbicie od odcinka wcześniej rysowanego(a lekkim zakrzywieniem - przypadkowym) aby uzyskać niewielki misz masz, może nawet nietypowy wygaszacz ekranu


(Kdryja) #5

Dzięki wszystkim za odpowiedzi.

Generalnie już wiem w czym mam błąd, ale niestety nie mam za bardzo pojęcia jak go rozwiązać, głównie przez niedobór wiedzy z matematyki. Program, który napisałem sprawdza punkt przecięcia PROSTYCH, na których leżą odcinki. Czego brakuje? Ano sprawdzenia czy ten punkt należy do danych odcinków i tu pojawia się problem, z którym nie potrafię sobie poradzić.

Mój program jeszcze nie bierze pod uwagę przypadku, gdyby odcinki byłby prostopadła do osi OX (Y1=Y2 lub Y3=Y4). Ale na to można rozpisać oddzielną formułkę.

Gorzej jeśli chodzi o sprawdzenie czy punkt należy do odcinka. Nawet w internecie żadnego wzoru znaleźć nie mogłem. Za wszelką pomoc i wskazówki jestem wam bardzo wdzięczny.


([alex]) #6

Ile będzie 2+2 też w internecie nie znajdziesz, bo to taki prymityw że nie warto temu poświęcić nawet wiersza na stronie:

if((Ax<=x)&&(x<=Bx)&&(Cx<=x)&&(x<=Dx)&&(Ay<=y)&&(y<=By)&&(Cy<=y)&&(y<=Dy))

* Pod warunkiem że Ax<=Bx Cx<=Dx Ay<=By Cy<=Dy, jeżeli nie to odpowiednio wymienić.