1096 Qtri

[•wefgef]

Aici puteti discuta despre problema Qtri.

[•Andrei.Xwe]

Am incercat sa rezolv problema prin metoda ariilor, dar nu iau decat 60 de puncte(WA pe 7 si 8, respectiv TLE pe 9,10).Rezultatul l-am verificat asa: fie a1 aria triunghiului ABC si a2,a3,a4 ariile triunghiurilor ABD, ACD, respectiv BCD.Conditia era (a2+a3+a4-0.03<=a1 && a1<=a2+a3+a4+0.03).De ce iau WA pe 7 si 8? Si exista vreo metoda mai rapida de a afla daca un punct se afla in interiorul unui triunghi decat metoda ariilor(presupun ca de asta iau TLE pe ultimele doua teste)?

[•pauldb]

O idee buna e sa folosesti formula cu determinant pentru a calcula aria triunghiului. Operatiile sunt mai rapide si poti evita folosirea numerelor in virgula mobila.

[•Andrei.Xwe]

Inainte faceam cu formula lui Heron cu semiperimetrul.Acum am incercat si a doua varianta de acolo, dar e exact acelasi rezultat.
P.S.:Am modificat si la conditii, a1==a2+a3+a4.

[•soriyn]

probabil ai probleme de precizie. nu e nevoie de float ci de int daca faci aria cu determinanti (singura conditie sa nu mai imparti la 2). din cate am vazut tu mai folosesti si sqrt pe acolo si cred ca n.ai inteles cum e cu determinantii astia. cauta pe net cum se calculeaza un determinant de ordin 3.

Poti sa faci si altfel. Ai 4 puncte deci poti forma 3 determinanti diferiti. Si daca au toti acelasi semn inseamna ca punctul e in interior.

[•Buzu_Tudor_Ro]

eu am rezolvat problema cu ajutorul determinantilor dar nu iau mai mult de 90 de pct ( ultimul test TLE ). exista vreo metoda mai rapida ??

Cod:

Program p2;
var i,n :longint;  bufi,bufa : array[0..1 shl 21] of char;
    x1,x2,x3,x4,y1,y2,y3,y4,k1,k2,k3:int64;
begin
    assign(input,'qtri.in'); reset(input);
    assign(output,'qtri.out'); rewrite(output);
    settextbuf(input,bufi); settextbuf(output,bufa);
    readln(n);
    for i:=1 to n do begin
                     read(x1,y1,x2,y2,x3,y3,x4,y4);
                     k1:=x1*y2+x2*y4+x4*y1
                         -x4*y2-x1*y4-x2*y1;
                     k2:=x2*y3+x3*y4+x4*y2
                         -x4*y3-x2*y4-x3*y2;
                     if (k1*k2<0) then writeln('NU')
                                  else begin
                                       k3:=x3*y1+x1*y4+x4*y3
                                           -x4*y1-x3*y4-x1*y3;

                                       if (k2*k3<0) or (k1*k3<0) then writeln('NU')
                                                               else writeln('DA');
                                       end;
                     end;
end.

[•SpiderMan]

Da, O(1) pe test cu arii .

[•soriyn]

Pai si cu determinanti nu e tot O(1) ?

[•SpiderMan]

Nu stiu, poate ii de la freepascal, fa cu settextbuff citirea.

[•PlayLikeNeverB4]

Nici nu te-ai obosit sa vezi ca asa face citirea?
Si i-a iesit de 100, dar n-a revenit cu un edit. Mergea prea incet fiindca facea operatiile pe long long.

[•lucian666]

   Salut. Am rezolvat problema cu metoda determinantilor insa iau doar 80 pct cu 2 TLE   .Mi se pare ca metoda asta e in O(1) ,deci nu ar trebui sa-mi dea TLE.
Vreo sugestie ceva ?
Multumesc Anticipat!!!!
L.E .Am pus long long peste tot(initial aveam double ) si a intrat de 100

[•otniel]

imi puteti explica si mie cum sta treaba cu determinantii astia?

[•SebiSebi]

Dacă ai trei puncte (x1,y1), (x2,y2), (x3,y3) atunci determinantul
|x1 y1 1|
|x2 y2 1| reprezinta dublul ariei triunghiului determinat de cele 3 puncte.
|x3 y3 1|
Dacă determinantul este strict pozitiv punctele sunt în sens trigonometric, dacă este strict negativ sunt în sens anti-trigonometric iar dacă este nul punctele sunt coliniare.
Aria triunghiului este:  |det|/2;

[•otniel]

multumesc mult