011 Copaci

[•junior]

Eu calculez nr de copaci cu teorema lui pick, cum ati zis si voi. Calculez aria, apoi nr de puncte de pe laturi si etc. Insa, iau WA pe primele 2 teste. Care sa fie problema? Sa fie din cauza ariei pe care nu am implementat-o cum zicea bogdan2412, ci cu determinanti? Sau testele respective au un caz special pe care eu nu l-am vazut?

[•filipb]

Sa nu rada nimeni de mine... Poate e banal ( sau poate e clasica ) si nu ma prind (sunt si obosit la ora asta...   ) Daca avem un segment de varfuri (x, y), (x[j], y[j]), toate numere intregi, de ce numarul de puncte laticiale (adik de coordonate intregi) de pe segment este cmmdc(|x-x[i-1]|, |y-y[i-1]|)?  


                                                       bubbleSORT

[•silviug]

+1

Dar tu foloseste formula pe care ai scris-o pentru a nu numara colturile poligonului de doua ori .

[•filipb]

...

[•cavendish]

ideea in mare e buna, doar ca cc = 14, nu -14 ... deci:
cc = - x1 * y2 + x2 * y1 = 14
se verifica usor refacand calculul, fie cu rapoarte, fie cu determinant. O sa vezi ca geometria e chiar misto stiind cateva proprietati ale inmultirii vectoriale, scalare, dar is si cativa determinanti ajutatori...
Numa bine

[•filipb]

Ms. mult de tot... m-ai scos dintr-o mare dilema... (m-am mai uitat intr-o carte si cc era intr-adevar x1 * y2 - x2 * y1, dar aa si bb erau cu semn schimbat acolo, deci la mine cc TREBUIA CU SEMN SCHIMBAT! )
  ms mult... raman dator  

  bubbleSORT

[•vladcyb1]

Am si eu o mare nelamurire. Pur si simplu de o zi ma chinui sa fac problema asta si nu inteleg de ce iau numai 40 de puncte pe primele 4 teste. Daca are cineva timp va rog sa aruncati o privire pe sursa mea sa-mi ziceti  si mie unde gresesc.

Cod:

...

Vlad

[•filipb]

Si eu luam tot 40 la un moment dat cu WA pe ultimele 6 teste. Problema era ca foloseam tipuri doar pe 32 de biti, in loc de tipuri pe 64. Incearca sa schimbi cu int64 ( daca lucrezi in Pascal ) sau cu long long ( pentru C/Cpp)..

  bubbleSORT

[•vladcyb1]

Mersi mult ! Asta a fost.

[•devilkind]

sursa de mai sus ar fi trebuit stearsa ptr a nu fi tendinte de copy paste 

[•filipb]

S-a sters 

[•k_ounu_eddy]

Am si eu o intrebare.Daca ai un poligon,cum il imparti in mai multe triunghiuri dreptunghice,sau in patrate?Cam cata matematica tre sa stii sa faci problema asta,mai mult de materia de clasa a 9a?

[•wefgef]

Teorema lui Pick iti garanteaza faptul ca A = B/2 + I - 1, unde A = aria poligonului, B = numarul de puncte laticeale de pe laturile poligonului, iar I = numarul de puncte laticeale din interiorul poligonului. Citeste pe net daca vrei mai multe detalii despre demonstratie. Implementarea nu depaseste nivelul clasei a 9a.

[•k_ounu_eddy]

Pai tocmai asta ma intereseaza pe mine.Trebuie sa aflu aria poligonului,si pt asta trebuie sa il impart in alte figuri carora sa le pot calcula aria(patrat ,triunghi,etc).Este cumva alta metoda?

[•wefgef]

Parcurgi varfurile poligonului in ordine, si ptr fiecare 2 puncte consecutive aduni p1.x*p2.y - p2.x*p1.y. Aria poligonolui va fi suma valorilor calculate astfel impartita la 2 si in modul.

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry1 uita-te la polygon area

[•k_ounu_eddy]

Mersi mult.

[•Tabara]

Dupa ce reusesti aria, mai trebuie doar sa stii ca numarul de puncte laticeale de pe un segment caracterizat de varfurile (x1,y1) si (x2,y2)  este Cmmdc( |x1-x2|, |y1-y2|) + 1 .

 

[•k_ounu_eddy]

Mai am o intrebare,ca de cat sa fac problema asa pe de rost,mai bine o inteleg.In aria unui poligon,de ex. ai 2 puncte consecutive,ce reprezinta p1.x*p2.y - p2.x*p1.y,aria triunghiului determinat de punctele alea sau ce?Cum dem asta?Va rog explicati-mi si mie

[•Tabara]

Formula pe care ti-a spus-o wefgef ester formula calcularii ariei unui poligon cu determinanti.

Este cam asa:

Uite daca ai spre exemplu sirul a[] care retine coordonatele punctelor care determina poligonul.

Cod:

double arie = 0;
a[n+1] = a[1];
for ( i = 1; i <= n; ++i )
    {
        arie += (a[i].x*a[i+1].y) - (a[i].y*a[i+1].x);
    }
arie /= 2;

[•k_ounu_eddy]

Da,asta o stiu.Dar pe mine ma intereseaza matematic.Ce sunt determinantii?

[•Tabara]

Da,asta o stiu.Dar pe mine ma intereseaza matematic.Ce sunt determinantii?

Hm...singurul lucru pe care te-as sfatui e sa iei un manual de a XI de matematica.Sunt foate bine explicati si nu iti ia mai mult de o ora - doua sa ii inveti cat de cat.

Uite un link daca vrei sa stai la comp in timp ce iti inveti (  )
http://mathworld.wolfram.com/Determinant.html

[•k_ounu_eddy]

Si daca inteleg ce sunt determinantii aia,inteleg si formula?La urma urmei o sa o intreb azi pe profa de mate,sa vad ce imi zice,ca momentan nush de unde sa fac rost de un astfel de manual

[•k_ounu_eddy]

Ok,am facut si eu ,dar iau 80 de p,pe ultimele 2 teste iau TLE.Sa vad ce mai pot sa optimiziez.
ps:de ce nu merge functia abs()?ca imi zice ca apelul functiei este ambiguu.Cred ca daca as reusi sa fac sa imi mearga ,miar intra in timp.

[•devilkind]

incearca sa implementezi functia abs la mana.

[•k_ounu_eddy]

Am facut functia abs inline,si tot imi iese din timp.Se poate sa imi iasa din timp din cauza ca folosesc clase,si incetineste timpul de exec?Tre sa folosesc printf si scanf?