Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 1096 Qtri  (Citit de 3753 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« : Decembrie 13, 2010, 00:40:44 »

Aici puteti discuta despre problema Qtri.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Andrei.Xwe
Strain
*

Karma: -4
Deconectat Deconectat

Mesaje: 38



Vezi Profilul
« Răspunde #1 : Aprilie 20, 2012, 07:05:08 »

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)?
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #2 : Aprilie 20, 2012, 07:17:54 »

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.
Memorat

Am zis Mr. Green
Andrei.Xwe
Strain
*

Karma: -4
Deconectat Deconectat

Mesaje: 38



Vezi Profilul
« Răspunde #3 : Aprilie 20, 2012, 14:00:42 »

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.
Memorat
soriyn
Vorbaret
****

Karma: 24
Deconectat Deconectat

Mesaje: 150



Vezi Profilul
« Răspunde #4 : Aprilie 20, 2012, 14:29:51 »

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.
Memorat
Buzu_Tudor_Ro
Strain


Karma: 21
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #5 : Aprilie 30, 2012, 15:39:09 »

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.
« Ultima modificare: Mai 01, 2012, 10:50:31 de către Mihai Calancea » Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #6 : Mai 01, 2012, 18:22:12 »

Da, O(1) pe test cu arii Smile.
Memorat
soriyn
Vorbaret
****

Karma: 24
Deconectat Deconectat

Mesaje: 150



Vezi Profilul
« Răspunde #7 : Mai 01, 2012, 19:24:12 »

Pai si cu determinanti nu e tot O(1) ? Whistle
Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #8 : Mai 01, 2012, 21:15:00 »

Nu stiu, poate ii de la freepascal, fa cu settextbuff citirea.
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #9 : Mai 01, 2012, 21:44:02 »

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.
Memorat
lucian666
Client obisnuit
**

Karma: 16
Deconectat Deconectat

Mesaje: 84



Vezi Profilul
« Răspunde #10 : Noiembrie 05, 2012, 23:01:10 »

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

Karma: -13
Deconectat Deconectat

Mesaje: 49



Vezi Profilul
« Răspunde #11 : Septembrie 13, 2013, 10:20:16 »

imi puteti explica si mie cum sta treaba cu determinantii astia?
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #12 : Septembrie 13, 2013, 11:20:53 »

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;
Memorat
otniel
Strain
*

Karma: -13
Deconectat Deconectat

Mesaje: 49



Vezi Profilul
« Răspunde #13 : Septembrie 13, 2013, 16:04:26 »

multumesc mult
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines