Zadanie ze spoj'a. Współliniowość punktów.

Question

--- kod zadania ze spoj ---

To zadanie: http://pl.spoj.com/problems/JWSPLIN/

Oto mój kod:

#include <iostream>

struct DirectionalForm{
    double a;
    double b;
};

DirectionalForm getDirectionalForm(double x[], double y[]); //obliczmy na podstawie dwóch punktów a i b ze wzoru: y = ax+b  
bool isSameLine(DirectionalForm dirFor, double x, double y); //sprawdzamy czy trzeci punkt spełnia to równianie 

int main(){
    int t;
    std::cin>>t;

    for(int i=0; i<t; i++){
        double x[3];
        double y[3];

        for(int i=0; i<3; i++){
            std::cin>>x[i]>>y[i];
        }

        auto dirFor = getDirectionalForm(x,y);

        //std::cout<<"y = "<<dirFor.a<<"x + "<<dirFor.b<<std::endl;

        if(isSameLine(dirFor,x[2],y[2]))
            std::cout<<"TAK"<<std::endl;
        else
            std::cout<<"NIE"<<std::endl;
    }
}

DirectionalForm getDirectionalForm(double x[], double y[]){
    DirectionalForm toRet;
    double divSub;

    //mamy wzory z tej stronki: https://www.matemaks.pl/rownanie-prostej-przechodzacej-przez-dwa-punkty.html
   
    if(y[0]-y[1] == 0 || x[0]-x[1] == 0) divSub = 0; //by nie doszło do błędu na wypadek np. 0/0
    else divSub = (y[0]-y[1])/(x[0]-x[1]);
    toRet.a = divSub;
    toRet.b = y[0]-divSub*x[0];
    return toRet;
}

bool isSameLine(DirectionalForm dirFor, double x, double y){
    return (dirFor.a*x + dirFor.b == y) ? true : false; //sprawdzamy trzeci punkt czy spełnia równanie y = ax + b 
}

Powiem krótko, program daje poprawne odpowiedzi i dla mojego kompilatora i dla kompilatora z jakiego korzysta serwis spoj: https://ideone.com/08Fy0m

W przykładzie na stronie mamy:

5
1	2	3	4	5	6
1	3	1	4	1	-3
1	2	-3	4	3	9
2	-1	3	-1	-4	-1
0	0	0	0	0 	0

Output:
TAK
TAK
NIE
TAK
TAK

dla " 1 3 1 4 1 -3 " jest to bzdura bo te trzy punkty nie są współliniowe :/

Wydaje mi się że wszystko działa poprawnie ale sędzia daje komunikat że błędna odpowiedź. Wiem że takich pytań dotyczących spoj'u jest sporo ale sami wiecie jaki to jest ból kiedy jesteście pewni że wszystko chodzi jak po maśle a sędzia nie akceptuje i nawet nie da znać dla jakich danych jest zły wynik :(

Dziękuje serdecznie za pomoc.

Comments

Moim zdaniem już na pierwszy rzut oka widać że ta seria jest na 1 linii. Wszystkie są na osi X na współrzędnej 1 i pod różnymi współrzędnymi Y. Tak więc program ma błąd.

Answer 1

Punkty są współliniowe, jeśli spełniony jest warunek:

(Xb - Xa) / (Yb - Ya)  = (Xc - Xa) / (Yc - Ya)

Jeśli mianownik (dzielnik) jednego ułamka = 0, to wystarczy zbadać drugi mianownik. Jeśli też = 0, to punkty są wspóliniowe.

To zadanie można rozwiązać w krótkiej funkcji main().

Comments

To chyba można sprowadzić do wyrażenia gdzie nie ma dzielenia ;)

---

Masz rację. Wtedy zadanie jeszcze się uprości.

---

@Beginer

Dziękuje za odpowiedź :) Okazało się że jeż samemu poradziłem sobie z problemem. Trochę za wcześnie daje pytania o pomoc zamiast samodzielnie myśleć. Kod teraz prezentuje się tak:

#include <iostream>

//------------------------------------------------------------------------------

struct Point{
    double x;
    double y;
};

//-----------------------------------------------------------------------------------

bool isSameLine(Point p[]){

    if(p[0].x == p[1].x){
        if(p[2].x == p[0].x)
            return true;
        else
            return false;
    }

     if(p[0].y == p[1].y){
        if(p[2].y == p[0].y)
            return true;
        else
            return false;
    }

    else{
        double a{(p[0].y-p[1].y)/(p[0].x-p[1].x)};
        double b{p[0].y-a*p[0].x};

        if(a*p[2].x+b==p[2].y)
            return true;
        else
            return false;
    }
}

//-----------------------------------------------------------------------------------

int main(){
    int t;
    std::cin>>t;

    for(int i=0; i<t; i++){
        Point point[3];

        for(int i=0; i<3; i++){
            std::cin>>point[i].x>>point[i].y;
        }

        if(isSameLine(point))
            std::cout<<"TAK"<<std::endl;
        else
            std::cout<<"NIE"<<std::endl;
    }
}

//--------------------------------------------------------------------------------------------------

Nadal problem jest zrobiony nieco na około ale skorzystam jeszcze z tego wzoru co podałeś:

(Xb - Xa) / (Yb - Ya)  = (Xc - Xa) / (Yc - Ya)

Za niego też daje naj ;)

Answer 2

dla " 1 3 1 4 1 -3 " jest to bzdura bo te trzy punkty nie są współliniowe :/

Jak to nie? Leżą na prostej x = 1. 

Comments

Racja, nie wiem co mnie opętało. Ale niby stosuje poprawny wzór :/ Muszę jeszcze wszystko wyliczyć na kartce.

---

Jakub 0 Wzór jest dobry, ale gdy masz w mianowniku dzielenie przez 0 (xa - xb) nie można przedstawić funkcji w postaci y(x) = ax+b (natomiast w postaci x(y) - np x = 1 - już tak). Masz taki wyjątek, któremu nie podoła funkcja getDirectionalForm. Więc musisz instrukcją if sprawdzić czy ten warunek (mianownik wyżej wspomnianego wyrażenia != 0) się zgadza zanim wywołasz funkcję. W else będziesz miał do sprawdzenia tylko czy trzeci punkt również jest na tej samej pionowej linii (czyli sprawdzenie x).