011 Copaci

[•svalentin]

da, foloseste printf scanf, merg mult mai repede decat cin cout!

[•Tabara]

Nu ar trebui sa folosesti labs ?
Ca din cate vad eu, N merge pana la 100 000.( desi pe evaluatorul asta int = long int  )

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

 

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

[•k_ounu_eddy]

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.

[•Bluedrop_demon]

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.

[•amadaeus]

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.

[•Bluedrop_demon]

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

[•floringh06]

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

[•Bluedrop_demon]

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

[•devilkind]

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.

[•Bluedrop_demon]

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

[•kino]

a facut cineva problema asta in pascal?mie imi iese din timp pe ultimul test 

[•hulparuadrian]

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??

[•wefgef]

Iei 40 de puncte din cauza ca nu lucrezi pe 64 de biti. Poti stoca datele linistit .

[•hulparuadrian]

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??

[•wefgef]

Vad ca ai luat 100 pana la urma . Care era problema cand luai 60?

[•hulparuadrian]

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 


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

[•bogdanhm999]

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.

[•DITzoneC]

Variabilele de tip long long se citesc cu %lld nu cu %ld.

[•thestick]

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.

[•stef2n]

Si ce-i asa gresit la formula ta?

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

[•wefgef]

Sa tot faci Pick fara sa stii dinainte .

[•thestick]

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.

[•mordred]

Daca se poate uita cineva pe sursa mea, stau de cateva ore pe problema asta. 
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.

[•toni2007]

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.

[•Sorin_Ionut]

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 

Multumesc anticipat !