[c++][SPOJ]Punkty w trójkącie

nerdzio
Użytkownik
Użytkownik
Posty: 29
Rejestracja: 1 kwie 2008, o 16:46
Płeć: Mężczyzna
Lokalizacja: St-ce
Podziękował: 3 razy
Pomógł: 1 raz

[c++][SPOJ]Punkty w trójkącie

Post autor: nerdzio »

Proszę o pomoc przy tym zadaniu, ponieważ rozwiązałem je i wydaje mi się że sposób jest prawidłowy (wysyłałem różne wersje z małymi modyfikacjami) ale spoj cały czas wywala WA. Kod jest bardzo prosty:

Kod: Zaznacz cały

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

int main()
{
    ios_base::sync_with_stdio(0);
    int xa,xb,xc,xp,ya,yb,yc,yp,pole1,pole2,pole3,pole;
    while(cin>>xa>>ya>>xb>>yb>>xc>>yc>>xp>>yp)
    {
            pole1=abs((xb-xa)*(yp-ya)-(yb-ya)*(xp-xa));
            pole2=abs((xp-xb)*(yc-yb)-(yp-yb)*(xc-xb));
            pole3=abs((xp-xa)*(yc-ya)-(yp-ya)*(xc-xa));
            pole=abs((xb-xa)*(yc-ya)-(yb-ya)*(xc-xa));
            
            //cout<<"pole1: "<<pole1<<"pole2: "<<pole2<<"pole3: "<<pole3<<"pole : "<<pole<<endl;
            if(xa==0 && xb==0 && xc ==0 && xp==0 && ya==0 && yb==0 && yc==0 && yp==0) break;
            else if (pole1==0 || pole2 == 0 || pole3==0) cout<<"E
"; // czy na trójkącie
            else if(pole1+pole2+pole3>pole) cout<<"O
"; // czy na zewnątrz
            else cout<<"I
"; //if(pole1+pole2+pole3 == pole) // czy wewnątrz                   
    }
return 0;
}
Liczę pola trójkątów i sprawdzam dzięki temu czy punkt należy do trójkąta.Licząc pole nie mnożę razy 0.5 dzięki czemu operuje na intach(long long też daje złą odpowiedź) Wszystkie testy przykładowe przechodzi.
Treść zadania:
matshadow
Użytkownik
Użytkownik
Posty: 941
Rejestracja: 17 gru 2007, o 21:48
Płeć: Mężczyzna
Lokalizacja: Kingdom Hearts
Podziękował: 6 razy
Pomógł: 222 razy

[c++][SPOJ]Punkty w trójkącie

Post autor: matshadow »

Nie wiem po co Ci pole, ale ja to rozwiązałem na bazie
nerdzio
Użytkownik
Użytkownik
Posty: 29
Rejestracja: 1 kwie 2008, o 16:46
Płeć: Mężczyzna
Lokalizacja: St-ce
Podziękował: 3 razy
Pomógł: 1 raz

[c++][SPOJ]Punkty w trójkącie

Post autor: nerdzio »

Liczę pole tego trójkąta którego punkty są podane i 3 innych utworzonych z podanego puntu i dwóch innych należących do tego pierwotnego trójkąta. Chciałbym rozwiązać to zadanie tym sposobem bo według mnie powinien on być dobry, jak nikt nie wskaże błędu to zrobię to tym twoim.



Czyli liczę pola ABC,ABX , ACX ,BCX i jeśli jedno z ABX , ACX ,BCX = 0 to wtedy punkt leży na boku ABC, jeśli ABX + ACX + BCX = ABC to leży wewnątrz i ostatni przypadek że na zewnątrz
Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

[c++][SPOJ]Punkty w trójkącie

Post autor: Dumel »

można też odpalić algorytm Grahama lub Jarvisa (wyszukiwanie otoczki wypukłej) dla czterech punktów.
trzy przypadki:
1. wszystkie punkty należą do otoczki
2. tylko punkty trójkąta należą do otoczki
3. pozostałe przypadki razem wzięte

dają trzy możliwe odpowiedzi
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

[c++][SPOJ]Punkty w trójkącie

Post autor: Zordon »

Dumel pisze:można też odpalić algorytm Grahama lub Jarvisa (wyszukiwanie otoczki wypukłej) dla czterech punktów.
trzy przypadki:
1. wszystkie punkty należą do otoczki
2. tylko punkty trójkąta należą do otoczki
3. pozostałe przypadki razem wzięte

dają trzy możliwe odpowiedzi
po co armata na muchę, wystarczy liczyć to z iloczynu wektorowego. Metoda z polami jest równie dobra ale pewnie masz błąd w kodzie, nie chce mi się tego sprawdzać, ale może jest problem z zakresem zmiennych.
Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

[c++][SPOJ]Punkty w trójkącie

Post autor: Dumel »

nie żebym twierdził że to najprostsze z możliwych rozwiązań
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

[c++][SPOJ]Punkty w trójkącie

Post autor: Zordon »

Dumel pisze:nie żebym twierdził że to najprostsze z możliwych rozwiązań
implementowalem kilka razy Grahama i chcę tego innym zaoszczedzić
półpasiec
Gość Specjalny
Gość Specjalny
Posty: 534
Rejestracja: 8 lip 2004, o 17:05
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 1 raz
Pomógł: 17 razy

[c++][SPOJ]Punkty w trójkącie

Post autor: półpasiec »

masz złą kolejność w warunkach
ODPOWIEDZ