[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 » 24 sie 2009, o 09:19

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: http://pl.spoj.pl/problems/T_PINTR/

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 » 24 sie 2009, o 14:40

Nie wiem po co Ci pole, ale ja to rozwiązałem na bazie tego

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 » 24 sie 2009, o 14:51

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.

http://www.picshot.pl/public/view/full/5030

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 » 24 sie 2009, o 15:23

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
Gość Specjalny
Gość Specjalny
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 909 razy

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

Post autor: Zordon » 24 sie 2009, o 15:52

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 » 24 sie 2009, o 16:13

nie żebym twierdził że to najprostsze z możliwych rozwiązań

Awatar użytkownika
Zordon
Gość Specjalny
Gość Specjalny
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 909 razy

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

Post autor: Zordon » 24 sie 2009, o 16:17

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 » 1 wrz 2009, o 01:13

masz złą kolejność w warunkach

ODPOWIEDZ