infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Dan-Leonard Crestez din Martie 08, 2004, 20:01:35



Titlul: 011 Copaci
Scris de: Dan-Leonard Crestez din Martie 08, 2004, 20:01:35
Aici puteţi discuta despre problema Copaci (http://infoarena.ro/problema/copaci).


Titlul: Răspuns: 011 Copaci
Scris de: TheWoolf din Martie 14, 2005, 16:31:21
cum da mah 21 exemplu??
mie imi da 14 asa facut de mana...nush...nu ma prind... :-k


Titlul: Răspuns: 011 Copaci
Scris de: Anton Alexandru din Martie 14, 2005, 22:21:56
Fa de mana si ai sa vezi !!! =;


Titlul: Răspuns: 011 Copaci
Scris de: TheWoolf din Martie 15, 2005, 00:29:46
pai am facut de mana si nam vazut.. :(


Titlul: Răspuns: 011 Copaci
Scris de: Marin Radu din Martie 15, 2005, 08:07:49
sigur ai folosit foaie de matematica?..si vezi sa nu le numeri pe alea care sunt pe granita..foloseste si o rigla ca sa-ti iasa bine poligonu'.


Titlul: Răspuns: 011 Copaci
Scris de: TheWoolf din Martie 15, 2005, 12:44:53
Ooops :mrgreen: ..my bad..
am desenat eu gresit...gata am luat 100...np..merge..e bine..


Titlul: Răspuns: 011 Copaci
Scris de: Constantin Cristian din Martie 18, 2005, 09:16:01
Cine imi spune mie cum merge exact algoritmul care verifica daca un punct apartine interiorului unui poligon oarecare?
    Daca numar toate punctele de intersectie de la dreapta punctului cu laturile poligonului imi da, dar ce se intampla daca dreapta intersecteaza un varf al poligonului?


    Si sa imi spuneti si mie daca acest algoritm s-ar putea adapta pentru aceasta problema. (Din punct de vedere al timpului de executie, pentru ca banuiesc ca altfel nu ar fi probleme).


Multumesc mult!!! :oops:


Titlul: Răspuns: 011 Copaci
Scris de: Marin Radu din Martie 18, 2005, 09:28:44
In primul rand varianta asta nu te ajuta la rezolvarea problemei. [-X
Dar pentru stiinta iti explic:

cand intalnesti un punct de pe poligon te uiti la cele doua segmente care il contin: daca ambele seg au celalalt capat de aceeasi parte a dreptei ignori intersectia, altfel o numeri. Mai exista cazul cand intalnesti segmente ale poligonului care sunt incluse in dreapta de scanare. Le ignori pur si simplu de parca nici n-ar exista. Ok?

Ar trebui sa-ti dea raspunsul corect...  :wink:


Titlul: Răspuns: 011 Copaci
Scris de: Marin Radu din Martie 18, 2005, 13:16:59
Testu' 2 e cu shmen? tot iau WA...daca se poate va rog sa mi-l postati...


Titlul: Răspuns: 011 Copaci
Scris de: Constantin Cristian din Martie 19, 2005, 13:25:42
Ce complexitate are solutia comisiei?

Imi da cineva si mie o indicatie?


Titlul: Răspuns: 011 Copaci
Scris de: Dima Alex din Martie 19, 2005, 15:17:54
probabil O(N) cu o ct destul de mica.

E o relatie matematica data de Teorema unui tip smecher  [-X . Nu-ti zic cum il cheama ca atunci ar fi prea evident... :P. Mai cauta relatii in triunghiul oarecare...


Titlul: Răspuns: 011 Copaci
Scris de: cristi8 din Martie 19, 2005, 15:32:00
Citat din mesajul lui: cavendish
probabil O(N) cu o ct destul de mica.

E o relatie matematica data de Teorema unui tip smecher  [-X . Nu-ti zic cum il cheama ca atunci ar fi prea evident... :P. Mai cauta relatii in triunghiul oarecare...


dc in triunghi oarecare ? ..nu merge cu "P***'s Theorem" ?


Titlul: Răspuns: 011 Copaci
Scris de: Cosmin Negruseri din Martie 19, 2005, 16:38:19
cmmdc are complexitate logaritmica deci solutia nu e chiar O(n)


Titlul: Răspuns: 011 Copaci
Scris de: Constantin Cristian din Martie 19, 2005, 23:47:00
Am cautat dar nu am auzit sa fi cercetat Pitagora sau altcineva cati copaci intra intr-un triunghi oarecare.
Am descoperit totusi ceva intre cmmdc si triunghiul dreptunghic ( atatea indicii am primit).
Si anume: numarul punctelor de coordonate intregi din interiorul unui triunghi cu varfurile de asemenea de coordonate intregi este:
[ (a-i)(b-1) - cmmdc(a, b) + 1]/2. Mi se pare chiar foarte corecta formula si nu cred ca e greu de gasit. Adica intru-un dreptunghi sunt (a - 1)(b - 1) puncte de coordonate intregi iar intr-un triunghi dreptunghic sunt  cam jumatate ( pentru ca scadem  numarul de puncte de pe diagonala dreptunghiului care au coordonate intregi).
Nu?
Se poate generaliza si la un triunghi oarecare daca este nevoie ( il incadrez intr-un dreptungi si scad punctele din cele 3 triunghiuri dreptunghice care apar).
Asa... si daca asta este formula pe care mi-ai cerut-o, atunci ce fac mai departe?


Titlul: Răspuns: 011 Copaci
Scris de: Cosmin Negruseri din Martie 20, 2005, 01:50:37
Ii zice teorema lui Pick, daca vrei sa citesti mai mult pe tema asta poti sa te uiti aici: http://www.geometer.org/mathcircles/pick.pdf . Mai trebuie sa ai grija la punctele de coordonate intregi care sunt pe laturile poligonului.


Titlul: Răspuns: 011 Copaci
Scris de: TheWoolf din Martie 20, 2005, 09:29:24
Ai stricat toata distractia...Booo!!! :x


Titlul: Răspuns: 011 Copaci
Scris de: Cosmin Negruseri din Martie 20, 2005, 09:59:51
Ce distractie? E problema daca stii sau nu teorema, oricum e de antrenament, cu ce esti mai tare ca ai auzit de teorema dinainte sau nu ...


Titlul: Răspuns: 011 Copaci
Scris de: Bogdan-Cristian Tataroiu din Martie 24, 2005, 13:37:37
Ok am calculat aria poligonului si numarul de puncte de coordonare intregi de pe laturi si apoi am folosit teorema lui Pick ca sa aflu numarul de puncte din interiorul poligonului. Aria am calculato cu formula cu determinanti si pentru numarul de puncte de pe laturi am folosit urm metoda: initial variabila B e 0 si luam laturile pe rand (inclusiv latura dintre punctul n si punctul 1) adunand de fiecare data cmmdc(|x-x[i-1]|,|y-y[i-1]|)... Mie mi se pare corecta rezolvarea dar totusi am primit WA la testu 5-10. Poate cineva sa ma ajute? ](*,)


Titlul: Răspuns: 011 Copaci
Scris de: Gogu Marian din Martie 24, 2005, 14:14:06
Testele 5-10 poti sa le iei daca faci doar aria poligonului, puncte fiind pe laturi parca doar la testele 1-4, cele care le iei(asa a fost la mine, dupa ce am ignorat varfurile aflate intre alte 2 varfuri).
Poate nu iei varfurile ca puncte de pe laturi, nu stiu ce sa zic.
Oricum, ti-au iesit testele mai grele, vezi ca poate nu iti merge cmmdc in unele cazuri, nu stiu.


Titlul: Răspuns: 011 Copaci
Scris de: Bogdan-Cristian Tataroiu din Martie 24, 2005, 15:02:43
Tu cum ai calculat aria poligonului? Am incercat de test sa scot cautarea punctelor pe laturi si am luat 0 puncte sa vad daca aici era problema, deci am gresit ceva la calcularea ariei...


Titlul: Răspuns: 011 Copaci
Scris de: Gogu Marian din Martie 24, 2005, 15:24:40
Aria am facut-o cu determinanti. Imparteam poligonul in n-1 triunghiuri cu varfuri in punctele p0 pi si pi+1. Tu cum faci?


Titlul: Răspuns: 011 Copaci
Scris de: Bogdan-Cristian Tataroiu din Martie 24, 2005, 15:36:50
Da aveam o greseala la calcularea ariei... Bine, eu inca nu m-am prins ce gresisem, dar pur si simplu am luat programul principal, am apasat delete si l-am scris din nou. :mrgreen: Multumesc pentru ajutor


Titlul: Răspuns: 011 Copaci
Scris de: Sara Nicolae Bogdan din Aprilie 19, 2005, 18:44:39
Aria o fac asa

Cod:

a[n+1] = a[1];

for (i =1 ; i<= n ; i++)
     aria+= a[i].x*a[i+1].y-a[i].y*a[i+1].x;

Pentru numarul punctelor de pe o latura fac
cmmdc(|a.x - a[i+1].x|,|a.y - a[i+1].y|)

Ce gresesc de nu iau ultimele 6 teste ?
Trebuie facut pe numere mari ? (desi nu cred , ca nu mai intra in timp)


Titlul: Răspuns: 011 Copaci
Scris de: Bogdan-Cristian Tataroiu din Aprilie 19, 2005, 19:04:05
Asa faceam si eu aria si nu-mi lua ultimele 6 teste. Dupa asta am facut aria cu metoda de pe TopCoder:
Cod:
    long x1,x2,y1,y2;
    for(i=1;i+1<n;i++)
    {
        x1=v[i].x-v[0].x;
        y1=v[i].y-v[0].y;
        x2=v[i+1].x-v[0].x;
        y2=v[i+1].y-v[0].y;
        S+=(double)x1*y2-(double)x2*y1;
    }
    S=fabs(S*0.5);
si a mers. Nu cred totusi ca asta era problema. Mai probabil era ca am gresit la implementare.


Titlul: Răspuns: 011 Copaci
Scris de: Sara Nicolae Bogdan din Aprilie 19, 2005, 20:06:28
Am incercat sa calculez asa si tot 40 iau ](*,)
Mersi oricum


Titlul: Răspuns: 011 Copaci
Scris de: Ovidiu Rosca din Aprilie 21, 2005, 21:07:37
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?


Titlul: Răspuns: 011 Copaci
Scris de: Filip Cristian Buruiana din Iunie 18, 2005, 20:46:16
Sa nu rada nimeni de mine... Poate e banal ( sau poate e clasica ) si nu ma prind (sunt si obosit la ora asta...  :oops: ) 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]|)?  :oops:


                                                       bubbleSORT


Titlul: Răspuns: 011 Copaci
Scris de: Silviu-Ionut Ganceanu din Iunie 22, 2005, 12:43:24
+1

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


Titlul: Răspuns: 011 Copaci
Scris de: Filip Cristian Buruiana din Iunie 24, 2005, 12:35:06
...


Titlul: Răspuns: 011 Copaci
Scris de: Dima Alex din Iunie 24, 2005, 14:24:13
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


Titlul: Răspuns: 011 Copaci
Scris de: Filip Cristian Buruiana din Iunie 24, 2005, 16:44:34
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


Titlul: Răspuns: 011 Copaci
Scris de: Vlad Berteanu din Iulie 11, 2005, 12:28:07
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


Titlul: Răspuns: 011 Copaci
Scris de: Filip Cristian Buruiana din Iulie 12, 2005, 02:53:31
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


Titlul: Răspuns: 011 Copaci
Scris de: Vlad Berteanu din Iulie 12, 2005, 08:29:06
Mersi mult ! Asta a fost. :P


Titlul: Răspuns: 011 Copaci
Scris de: Savin Tiberiu din Iulie 25, 2006, 08:07:55
sursa de mai sus ar fi trebuit stearsa ptr a nu fi tendinte de copy paste  ???


Titlul: Răspuns: 011 Copaci
Scris de: Filip Cristian Buruiana din Iulie 25, 2006, 11:23:16
S-a sters  :)


Titlul: Răspuns: 011 Copaci
Scris de: Iacob Eduard din Februarie 28, 2007, 22:57:51
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? :shock:


Titlul: Răspuns: 011 Copaci
Scris de: Andrei Grigorean din Februarie 28, 2007, 23:09:32
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.


Titlul: Răspuns: 011 Copaci
Scris de: Iacob Eduard din Februarie 28, 2007, 23:51:17
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?


Titlul: Răspuns: 011 Copaci
Scris de: Andrei Grigorean din Martie 01, 2007, 00:05:32
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


Titlul: Răspuns: 011 Copaci
Scris de: Iacob Eduard din Martie 01, 2007, 00:15:44
Mersi mult.


Titlul: Răspuns: 011 Copaci
Scris de: Tabara Mihai din Martie 01, 2007, 09:51:45
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 .

 :thumbup:


Titlul: Răspuns: 011 Copaci
Scris de: Iacob Eduard din Martie 01, 2007, 09:54:12
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


Titlul: Răspuns: 011 Copaci
Scris de: Tabara Mihai din Martie 01, 2007, 09:58:21
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;


Titlul: Răspuns: 011 Copaci
Scris de: Iacob Eduard din Martie 01, 2007, 10:01:12
Da,asta o stiu.Dar pe mine ma intereseaza matematic.Ce sunt determinantii?


Titlul: Răspuns: 011 Copaci
Scris de: Tabara Mihai din Martie 01, 2007, 10:05:56
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 (  :D )
http://mathworld.wolfram.com/Determinant.html


Titlul: Răspuns: 011 Copaci
Scris de: Iacob Eduard din Martie 01, 2007, 10:08:06
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


Titlul: Răspuns: 011 Copaci
Scris de: Iacob Eduard din Martie 01, 2007, 12:11:05
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.


Titlul: Răspuns: 011 Copaci
Scris de: Savin Tiberiu din Martie 01, 2007, 12:19:30
incearca sa implementezi functia abs la mana.


Titlul: Răspuns: 011 Copaci
Scris de: Iacob Eduard din Martie 01, 2007, 12:34:17
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?


Titlul: Răspuns: 011 Copaci
Scris de: Valentin Stanciu din Martie 01, 2007, 13:40:10
da, foloseste printf scanf, merg mult mai repede decat cin cout!


Titlul: Răspuns: 011 Copaci
Scris de: Tabara Mihai din Martie 01, 2007, 15:29:33
Nu ar trebui sa folosesti labs ?
Ca din cate vad eu, N merge pana la 100 000.( desi pe evaluatorul asta int = long int  :-k )

Oricum ar mai fi varianta Cmmdc-ului binar, desi nu stiu daca te ajuta prea mult.

 :thumbup:

[Later Edit] Nu cred ca e nevoie de Cmmdc binar.Cu scanf si printf ar trebui sa iti intre in timp. :thumbup:


Titlul: Răspuns: 011 Copaci
Scris de: Iacob Eduard din Martie 01, 2007, 18:34:18
Nu stiam ca este abs si labs(abs pt long).
Am intrebat azi si la mate.Totusi profesoara mi-a aratat cum se calculeaza un determinant de ala.
Intrebarea mea este:ce reprezinta p1.x*p2.y - p2.x*p1.y,macar sa inteleg asa intuiti.De ce daca fac operatia aia pt oricare 2 puncte imi da aria.De ex pt un triunghi?
Ps:sper ca nu sunt insistent.
[LE]Am luat in sfarsit 100 puncte.Ciudat.Prima data alocam in heap si nu se incadra,si apoi am alocat normal si am luat maximum de puncte.Si am folosit stdio.h.


Titlul: Răspuns: 011 Copaci
Scris de: Pandia Gheorghe din Martie 30, 2007, 20:45:21
Am facut problema dar imi cade pe primele 4 teste. Conform a ceea ce s-a scris mai sus, cele care au puncte pe laturi. Intr-adevar,  nu conteaza ca modificari fac asupra numarului de puncte de pe latura, iau mereu testele 5-10, deci am dedus ca acolo e 0. Desi am verificat, vreau totusi sa va rog sa va aruncati o privire asupra functiei cmmdc sa-mi ziceti daca nu cumva nu mai stiu sa fac o functie asa elementara:
Cod:
long cmmdc( long x, long y )
{
     if( ( x == 0 ) ) return y;
     if( ( y == 0 ) ) return x;
     long r, a, b;
     if( x > y ) { a = x; b = y; }
     else { a = y; b = x; }
     r = a%b;
     while( r )
            {
                 a = b;
                 b = r;
                 r = a%b;                 
            }
     return b;
}
Va multumesc!

LE: Am verificat pe mai multe cazuri si pare sa fie ok, chiar si da numarul de puncte cerut. Aria o fac cu formula de pe TopCoder dar nu pricep de ce ia numai ultimele 6 teste, adica B -ul imi da bine dar A-ul ramane urias, chiar si pe exemplu (unde imi da gresit).... nu pricep.

LE: Pentru moderatori / propunatori : cred ca evaluatorul e busit rau. Daca va uitati pe sursa mea veti vedea ca afisez o variabila neintializata si iau 50p. Iar daca nu afisez "long long" iau zero, chiar daca valoarea variabilei intra in long. De exemplu daca trimit o sursa in care calculez I (pick's th) in long si afisez cu "%ld" iau zero, daca afisez cu "%lld" (o variabila long normal) iau iarasi 50.


Titlul: Răspuns: 011 Copaci
Scris de: Lucian Boca din Aprilie 01, 2007, 21:33:21
E corect, dar te complici prea mult in calculul cmmdc. Poti face, de ex:
Cod:
int cmmdc( int a, int b ) {
int r;
while( b ) {
r = a % b;
a = b;
b = r;
}
return a;
}

Din cate tin minte, ca sa iei 100 trebuie lucrat cu intregi pe 64 de biti.


Titlul: Răspuns: 011 Copaci
Scris de: Pandia Gheorghe din Aprilie 01, 2007, 21:38:38
Io nu inteleg de ce iau pana si pe exemplu gresit... Adica ultimele 5 teste le iau scriind o variabila neintializata din stiva, care poate fi orice valoare si primele 4 le pic (cum de altfel credeam ca se va intampla cu toate avand in vedere ca nu merge exemplul)...

Am incercat de mai multe ori si sincer nu pricep...  :sad:


Titlul: Răspuns: 011 Copaci
Scris de: Florin Ghesu din Aprilie 02, 2007, 22:28:33
Am si eu o mica incurcatura la problema asta :)... eu lucrez pe pascal si iau tle pe ult 3 teste... am scris sursa in cpp(unde nu ma prea descurc) si ia wa pe ult 6 teste...ideea de rezolvare e strict aceeasi...dar pe c am observat ca la teste mari depaseste tipul...
eu a declarat long long...e altceva mai tare sau ce ar trebui sa fac? mersi :D


Titlul: Răspuns: 011 Copaci
Scris de: Pandia Gheorghe din Aprilie 03, 2007, 16:56:59
Imi spune si mie cineva va rog de ce urmatorul cod :
Cod:
    long long I, A, B;
    long x1, x2, y1, y2, c1, c2;
    A = 0;
    B = 0;
    for( i=2;i<n; i++ )   
         {
              x1 = p[i][0] - p[1][0];
              y1 = p[i][1] - p[1][1];
              x2 = p[i+1][0] - p[1][0];
              y2 = p[i+1][1] - p[1][1];
              A += x1*y2 - x2*y1;
         }
    if( A < 0 ) A = -A;
    A = A/2;
unde varfurile sunt memorate in p de la 1 la n, p[ i ][ 0 ] = x si p[ i ][ 1 ] = y nu da aria corecta  :'( ?

Iau numai ultimele 6 teste...


Titlul: Răspuns: 011 Copaci
Scris de: Savin Tiberiu din Aprilie 03, 2007, 17:14:59
nu prea inteleg ce folosesti tu acolo ptr calculul ariei. Banuiesc ca imparti in triunghiuri, incearca formula cu determinanti ptr tot poligonul direct, fara sa mai imparti in triunghiuri.


Titlul: Răspuns: 011 Copaci
Scris de: Pandia Gheorghe din Aprilie 03, 2007, 17:19:02
Este intr-adevar o impartire in triunghiuri, luata de pe TopCoder. Sunt mai multe post-uri cu ea si la toata lumea pare sa functioneze (pana am dat io de ea  :sad: ) . Formula cu determinanti nu sare din timp ? O sa o implementez si pe aceea dar as vrea sa stiu ce e in neregula cu calculul de mai sus ca sa stiu daca ma pot baza pe formula respectiva sau nu.

Multumesc mult pt sfat oricum.  :wink:


Titlul: Răspuns: 011 Copaci
Scris de: Ionescu Victor-Cristian din Aprilie 27, 2007, 16:05:47
a facut cineva problema asta in pascal?mie imi iese din timp pe ultimul test  :oops:


Titlul: Răspuns: 011 Copaci
Scris de: hulparu adrian din Februarie 20, 2008, 14:20:46
am si eu o intrebare...pentru punctaj maxim calcularea ariei si a numarului de pct laticiare de pe laturi se face direct din citire ?sau se pot stoca coordonatele punctelor date in fisierul de intrare in doi vectori...k io am fakut direct din citire si iau doar 40... :)probabil k ma incurc la aflarea ariei si a nr de pcte??


Titlul: Răspuns: 011 Copaci
Scris de: Andrei Grigorean din Februarie 20, 2008, 14:59:27
Iei 40 de puncte din cauza ca nu lucrezi pe 64 de biti. Poti stoca datele linistit :).


Titlul: Răspuns: 011 Copaci
Scris de: hulparu adrian din Februarie 20, 2008, 15:28:07
ms mult pt sfat...dah akum nu mai iau primele 4 teste...iau WA pe ele ... desi prima data am luat OK si WA pe ultimele 6...de ce?? ???


Titlul: Răspuns: 011 Copaci
Scris de: Andrei Grigorean din Februarie 20, 2008, 17:45:47
Vad ca ai luat 100 pana la urma :). Care era problema cand luai 60?


Titlul: Răspuns: 011 Copaci
Scris de: hulparu adrian din Februarie 20, 2008, 18:01:49
foloseam labs() pt a calcula modul din "long long"(determinarea ariei...) si am schimbat cu un banal "if..then"+fctia cmmdc am declarat-o pe int-uri...si akum merge...ms  :winner1:


"In fiecare zi inveti un lucru nou..."


Titlul: Răspuns: 011 Copaci
Scris de: Casu-Pop Bogdan din Martie 06, 2008, 14:12:43
iau WA pe testul 9, am facut calcularea ariei si cmmdc cum s-a descris mai sus si tot asa. Stie cnv de la ce ar fi?
si folosesc operatii pe 64b.


Titlul: Răspuns: 011 Copaci
Scris de: Adrian Diaconu din Martie 06, 2008, 18:24:27
Variabilele de tip long long se citesc cu %lld nu cu %ld.


Titlul: Răspuns: 011 Copaci
Scris de: Tudor A din Martie 12, 2008, 16:37:59
aceeasi sursa, punctaje diferite:
http://infoarena.ro/job_detail/155658 90p
http://infoarena.ro/job_detail/156174 100p
se pare ca formula mea gresita functioneaza. :)


Titlul: Răspuns: 011 Copaci
Scris de: Stefan Istrate din Martie 12, 2008, 17:15:41
Si ce-i asa gresit la formula ta? :)

P.S. Am mutat mesajul asta din "Feature request".


Titlul: Răspuns: 011 Copaci
Scris de: Andrei Grigorean din Martie 12, 2008, 18:35:55
Sa tot faci Pick fara sa stii dinainte :).


Titlul: Răspuns: 011 Copaci
Scris de: Tudor A din Martie 12, 2008, 20:15:46
deci iau poligonul , si daca gasesc o intoarcere la dreapta, sterg nodul din mijloc, si adun aria triunghiului eliminat la o variabila. si teoretic, imi ramane un soi de infasuratoare convexa in stiva, dupa aia calculez aria infasuratorii convexe, si o scad din prima variabila, si dupa aia calculez numarul de puncte laticeale de pe margine, si am toate elementele necesare pentru formula. stiu ca imi da gresit, pentru ca mi-am facut un caz nasol pe hartie (un fel de spirala) in care nu imi calculeaza bine, pentru ca se intersecteaza niste arii de triunghiuri. si totusi imi da...

si da, stiu ca exista o metoda mult mai usoara si mai scurta pentru a calcula aria unui poligon neconvex, dar e o sursa veche, scrisa inainte sa citesc despre geometrie computationala.


Titlul: Răspuns: 011 Copaci
Scris de: Simionescu Andrei din Iulie 16, 2008, 17:28:02
Daca se poate uita cineva pe sursa mea, stau de cateva ore pe problema asta.  ](*,)
http://infoarena.ro/job_detail/199034 (http://infoarena.ro/job_detail/199034)
Nu ia primele 4 teste, si pe input-ul:
Cod:
4
1 1
2 1
2 2
1 2
da raspunsul -2.


Titlul: Răspuns: 011 Copaci
Scris de: Pripoae Teodor Anton din Ianuarie 16, 2009, 13:42:27
Testul 9 nu corespunde limitelor problemei. O coordonata x depaseste 2 miliarde sau este mai mica de cat 0. Am  bagat un assert si crapa fix pe chestia aia. Cand am scos assert-ul a mers. Nu ca m-ar deranja asta, dar ar trebui modificat enuntul, daca nu se poate reface testul si baga o reevaluare.

Toni.


Titlul: Răspuns: 011 Copaci
Scris de: BYSorynyos din Martie 03, 2009, 12:25:05
Tot iau 40p iat la testele 5-10 WA si nu ma prind de ce  ](*,)
Se poate uita cineva pe sursa asta

Cod:
 

#include <stdio.h>

#define max 100011
#define IN "copaci.in"
#define OUT "copaci.out"

// I + B/2 - 1 = A
// A - arie
// I - interior
// B - laturi



Am sters codul pt a evita copy-paste-ul  :P

Multumesc anticipat !


Titlul: Răspuns: 011 Copaci
Scris de: Gabriel Bitis din Martie 03, 2009, 14:56:07
Foloseste long long.


Titlul: Răspuns: 011 Copaci
Scris de: BYSorynyos din Martie 03, 2009, 16:12:42
Foloseste long long.

Bun sfat acum iau ultimele 6 teste dar primele nu mai merg (e chiar ceva ciudat)  :P

S-a rezolvat foloseam unsigned long long , dar valorile puteau fi si negative  :fool:
 Multam'


Titlul: Răspuns: 011 Copaci
Scris de: Dragos din Iulie 23, 2010, 12:46:44
Salut!
 
Imi poate explica si mie cineva de ce imi apar probleme la convertirea in double(sau float).
Pentru aceasta bucata de  cod primesc 0 puncte.
Cod:
   double arie;
   double B;    


 if (arie < 0)
        arie = - arie;
     arie-=B;
     arie+=2;
    
    fout << (double)arie/2;  //iar daca schimb cu (float) sau nu sterg (double) tot 0 iau.

Iar pentru aceasta primesc 100(desi nu e normal sa impart asa la 2)
Cod:
   long long arie;
   long long B,N;  


if (arie < 0)
     arie = - arie;
fout << ((arie - B) >> 1) + 1;


Titlul: Răspuns: 011 Copaci
Scris de: Simoiu Robert din Iulie 23, 2010, 12:56:25
Cred ca stiu care e problema : daca faci ca in primul caz, rezultatul va fi afisat cu zecimale, iar in cazul in care numarul se imparte exact, numarul o sa fie de forma : X.000.. Dupa cum am citit problema, cred ca rezultatul trebuie sa fie intreg .


Titlul: Răspuns: 011 Copaci
Scris de: Dragos din Iulie 23, 2010, 13:24:52
Cred ca stiu care e problema : daca faci ca in primul caz, rezultatul va fi afisat cu zecimale, iar in cazul in care numarul se imparte exact, numarul o sa fie de forma : X.000.. Dupa cum am citit problema, cred ca rezultatul trebuie sa fie intreg .
Posibil.
Eu rulez in windows(am probleme cu linux-ul) si nu imi afiseaza cu 0-uri.

LE. Nici nu trebuie sa afiseze cu 0-uri probabil il linux afiseaza cu 0-uri.


Titlul: Răspuns: 011 Copaci
Scris de: Simoiu Robert din Iulie 23, 2010, 13:31:51
Pune asa : fout << setprecision ( 0 ) << fixed , si introduci : #include <iomanip>


Titlul: Răspuns: 011 Copaci
Scris de: Robert Badea din Decembrie 06, 2010, 23:01:44
Huh? Pot fi si negative? In cerinta scrie clar [0; ...


Titlul: Răspuns: 011 Copaci
Scris de: Bodnariuc Dan Alexandru din Iulie 22, 2012, 18:03:13
eu incerc sa rezolv problema impartind poligonul in triunghuri si calculand pt fiecare nr de puncte din interiorul lui..numa ca nam idee cum sa impart un poligon concav


Titlul: Răspuns: 011 Copaci
Scris de: Dumitru Andrei Georgian din Iulie 22, 2012, 18:11:09
Nu trebuie sa imparti nimic. Solutia foloseste teorema lui Pick. Citeste putin despre aceasta teorema si incearca sa rezovi dupa  :wink:
http://en.wikipedia.org/wiki/Pick's_theorem


Titlul: Răspuns: 011 Copaci
Scris de: Bodnariuc Dan Alexandru din Iulie 22, 2012, 18:18:15
am inteles ca se poate si cu teorema lui pick ,dar eu sunt curios cum se face cu ideea mea,adica cum se imparte un poligon concav in triughiuri


Titlul: Răspuns: 011 Copaci
Scris de: Dan H Alexandru din Iulie 24, 2012, 08:30:09
O posibila rezolvare la ce ai cerut tu cred ca iti pot oferi , sau , daca nu sunt destul de explicit , cel putin o idee. Pornesti dintr-un punct si parcurgi laturile 2 cate 2 si trasezi cate daca dreapta respectiva nu va fi trasata in exteriorul poligonului. Apoi mergi pe dreptele trasate si repeti operatia pana ai numai triunghiuri. Pe hartie am facut si cateva exemple  cu 3-4 pasi si mi se pare ca ar merge. Problema e la implementat...


Titlul: Răspuns: 011 Copaci
Scris de: Oancea Catalin din August 22, 2012, 21:52:32
Primesc WA pe toate testele  ](*,). Nu stiu ce poate fi gresit. Imi merg toate testele bagate de mine si folosesc long long. De la ce ar putea fi?

Job detail 780978 (http://infoarena.ro/job_detail/780978).


Titlul: Răspuns: 011 Copaci
Scris de: Visan Radu din August 22, 2012, 23:07:31
Afiseaza rezultatul final fara zecimale si iei 100 de pct.


Titlul: Răspuns: 011 Copaci
Scris de: Oancea Catalin din August 22, 2012, 23:17:19
Da...asta era.
Multumesc!  :)


Titlul: Răspuns: 011 Copaci
Scris de: Bratie Fanut din Februarie 22, 2013, 16:20:35
Am sursa asta pt problema "Copaci":
Cod:
#include <fstream>
#include <stdlib.h>
using namespace std;

........
 
   g<<p;
    f.close();
    g.close();
    return 0;
}
Obtin doar 60 de puncte, pe primele 4 teste iau WA. imi poate sugera cineva ceva?
LE: cod sters pt a evita copy-paste.


Titlul: Răspuns: 011 Copaci
Scris de: Laurentiu Ion din Februarie 23, 2013, 00:07:29
Am sursa asta pt problema "Copaci":
Cod:
#include <fstream>
#include <stdlib.h>
using namespace std;

struct punct
{
    long long x, y;
};
punct v[100001];

long long n,i,a,b;

long long cmmdc( long long a, long long b )
{
long long r;
while( b )
{
r = a % b;
a = b;
b = r;
}
return a;
}


int main()
{
    ifstream f("copaci.in");
    ofstream g("copaci.out");

    f>>n;
    for(i=1;i<=n;i++)
    f>>v[i].x>>v[i].y;

    b=0;
    for(i=1;i<n;i++)
    b+=cmmdc(llabs(v[i].x-v[i+1].x),llabs(v[i].y-v[i+1].y));

     long long x1,x2,y1,y2;
    for(i=1;i+1<n;i++)
    {
        x1=v[i].x-v[0].x;
        y1=v[i].y-v[0].y;
        x2=v[i+1].x-v[0].x;
        y2=v[i+1].y-v[0].y;
        a+=x1*y2-x2*y1;
    }
    a=llabs(a*0.5);

    long long p=a-(b/2)+1;
    g<<p;
    f.close();
    g.close();
    return 0;
}
Obtin doar 60 de puncte, pe primele 4 teste iau WA. imi poate sugera cineva ceva?

trebuie sa iei si perechea (n,1)
adica in for i<=n unde v[ n+1 ] = v[ 1 ]


Titlul: Răspuns: 011 Copaci
Scris de: Bratie Fanut din Februarie 23, 2013, 15:29:41
multumesc am luat 100 =D&gt;


Titlul: Răspuns: 011 Copaci
Scris de: Marin Cristian din Ianuarie 13, 2014, 18:22:34
nu se incadreaza in timp -_-. va rog sa ma scuzati ca v-am luat 0,01 secunde din viata. :P :))


Titlul: Răspuns: 011 Copaci
Scris de: noname din Ianuarie 19, 2014, 21:56:43
am doar 60 de p , primele 4 WA , spuneti-mi va rog care ii eroare
 ](*,)
program p1;
var a,b:array[0..100002] of longint;
    b3,b2:array[0..1 shl 17 ] of char;
    f,g:text;
    i,n,j,k,m,x,y,a1,b1:longint;
    aria,nr:int64;
function  cmmdc(a1,b1:longint):longint;
begin
if (a1=0) or ( b1=0) then cmmdc:=b1
             else cmmdc:=cmmdc(b1,a1 mod b1);
end;
begin
assign(f,'copaci.in');settextbuf(f,b3);reset(F);
assign(g,'copaci.out');settextbuf(g,b2);rewrite(G);
readln(f,n);
for i:=1 to n do
        readln(f,a,b);
a[n+1]:=a[1];
b[n+1]:=b[1];
for i:=1 to n do begin
        aria:=aria + (a*b[i+1]-b*a[i+1]);
        nr:=nr+cmmdc(abs(a-a[i+1]),abs(b-b[i+1]));
                end;
aria:=abs(aria div 2);
write(g,aria-(nr div 2) +1 );
close(F);
close(G);
end.


Titlul: Răspuns: 011 Copaci
Scris de: Andi Arnautu din August 08, 2014, 14:52:35
Imi pare bine ca am dat de aceasta problema, nu stiam de teorema lui Pick inainte. :)


Titlul: Răspuns: 011 Copaci
Scris de: Bosinta Alexandru din Aprilie 01, 2015, 10:33:56
Deci eu nu inteleg ce gresesc. As pune sursa dar ar lasa tentative de copy paste...
folosesc si long long int, pun rezultatul intrun numar intreg si apoi il afisez si tot iau 40p. pe ultimele 6 iau 0...


Titlul: Răspuns: 011 Copaci
Scris de: Mercea Otniel din Aprilie 20, 2017, 10:57:03
eu la problema asta am folosit long long pentru arie in loc de double si am luat 100. De ce functioneaza si cu long long? Sunt gresite testele sau nu conteaza, iar daca nu conteaza de ce merge?


Titlul: Răspuns: 011 Copaci
Scris de: Mouse Wireless din Octombrie 05, 2018, 22:13:29
Citat
Coordonatele copacilor au valori intregi din intervalul [0, 2.000.000]
Asta inseamna ca inmultirea coordonatelor ar trebui facuta pe tipuri de date pe 64 de biti (i.e. long long in C/C++), dar sunt multe surse care iau 100 de puncte desi opereaza cu tipuri de date pe 32 de biti. Interesant ca nu este niciun test care sa verifice asta  :ok: