Titlul: 1096 Qtri Scris de: Andrei Grigorean din Decembrie 13, 2010, 00:40:44 Aici puteti discuta despre problema Qtri (http://infoarena.ro/problema/qtri).
Titlul: Răspuns: 1096 Qtri Scris de: Cobzaru Adrian-Andrei din 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)?
Titlul: Răspuns: 1096 Qtri Scris de: Paul-Dan Baltescu din Aprilie 20, 2012, 07:17:54 O idee buna e sa folosesti formula cu determinant (http://infoarena.ro/notiuni-de-geometrie-si-aplicatii/arii) pentru a calcula aria triunghiului. Operatiile sunt mai rapide si poti evita folosirea numerelor in virgula mobila.
Titlul: Răspuns: 1096 Qtri Scris de: Cobzaru Adrian-Andrei din 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. Titlul: Răspuns: 1096 Qtri Scris de: Sorin Rita din 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. Titlul: Răspuns: 1096 Qtri Scris de: Cont vechi din 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. Titlul: Răspuns: 1096 Qtri Scris de: Simoiu Robert din Mai 01, 2012, 18:22:12 Da, O(1) pe test cu arii :).
Titlul: Răspuns: 1096 Qtri Scris de: Sorin Rita din Mai 01, 2012, 19:24:12 Pai si cu determinanti nu e tot O(1) ? :-'
Titlul: Răspuns: 1096 Qtri Scris de: Simoiu Robert din Mai 01, 2012, 21:15:00 Nu stiu, poate ii de la freepascal, fa cu settextbuff citirea.
Titlul: Răspuns: 1096 Qtri Scris de: George Marcus din 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. Titlul: Răspuns: 1096 Qtri Scris de: Vasilut Lucian din Noiembrie 05, 2012, 23:01:10 :) 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 :ok: Titlul: Răspuns: 1096 Qtri Scris de: Mercea Otniel din Septembrie 13, 2013, 10:20:16 imi puteti explica si mie cum sta treaba cu determinantii astia?
Titlul: Răspuns: 1096 Qtri Scris de: Pirtoaca George Sebastian din 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; Titlul: Răspuns: 1096 Qtri Scris de: Mercea Otniel din Septembrie 13, 2013, 16:04:26 multumesc mult
|