047 Trapez

[•domino]

Aici puteţi discuta despre problema Trapez.

[vladut.forum]

auleu, n-am nici o idee, (doarO(n^4))
pressupun ca O(n^2) ar fii destul de bun.
dati-mi si mie un hint, ca daca era sa descoper cate paralelograme sunt era mai simplu, (s-a dat la .Campion), da la trapeze nu mai merge faza.
sau poate sa mentin ideea de la paralelograme, astfel incat cand iau doua puncte, mijlocul il pun mai imaginar, adica pun mijlocul unde ar tb sa fie daca acel segment ar fii de lungime maxima, adica consider ca toate segmentele sunt egale, pot spune egale cu cel mai mare segment...
adica daca am segmentu [------] este de lungime 6, dar segmentul maxim are lungimea 8, sa spunem deci am sa pun mijlocul [----|--] sau [--|-----], da nu cred ca merge...infine datimi un hint mc

[•vladcyb1]

Eu am facut problema asa:
 am luat oricare 2 puncte, le-am calculat panta, am sortat pantele si de aici de descurci tu. Oricare 2 pante egale determina un trapez.  

[vladut.forum]

aha ai dreptate, mc mult, la paralelograme e, iei oricare 2 puncte si retii mijlocul, sortezi vectorul cu mijloacele, si te descurci mai departe...

da mai uite ca nu m-am gandit

[vladut.forum]

mah tu cum calculezi panta, ca eu o calculez asa
fac sin, cu dreapta care intersecteaza punctul cel mai de jos si e paralela cu Ox,
si lucrez in sin ^ 2, ca sa nu intru in double
a=y-y[j];
a=a*a;
b=distanta dintre punctul i, si punctul j
etc

[•vladcyb1]

Considerand doua puncte, unul de coordonate Xa,Ya si altul de coord Xb,Yb , panta dreptei pe care se afla aceste doua puncte este:

 m=(Yb-Ya)/(Xb-Xa);

[•filipb]

Bineinteles ca mai exista un caz particular daca faci asa: trebuie sa consideri si cand dreapta ta este paralela cu Oy, adica Xa = Xb...

[vladut.forum]

dap, le consider si pe alea, astea paralele le numar separat, adica numarparalele OX si numar si paralele OY
las si eu codul poate imi spune careva unde gresesc...

eu determin panta ca fiind patratul sinusul unghiului dintre segment si OX
am vectorii p1[] si p2[], cu semnificatia panta(i)=p1/p2;
obs ca la un moment dat imultesc cu -1, pt ca segmentul are alta orientare... adika asa / sau \ asa...
unu-numar alea paralele cu Oy
doi-numar alea paralele cu Ox

Cod:

for (i=0; i<n-1; i++)
     for (j=i+1; j<n; j++) {
          if (x[i]-x[j]==0) unu++;
          else if (y[i]-y[j]==0) doi++;
          else {
                 a=(y[i]-y[j]);
                 b=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
                 p1[k]=a*a;
                 if (x[i]<x[j]&&y[i]>y[j]) p1[k]*=-1;
                 else if (x[i]>x[j]&&y[i]<y[j]) p1[k]*=-1;
                 p2[k]=b;k++;
                 }
         }

dupa asta sortez cu qsort, sortarea e buna, garantez...
apoi
gasesc solutia ca fiind,
la un moment dat caut cea mai mare succesiune de pante egale,
si numarul trapezelor v-a creste cu n*(n-1)/2; unde n-lungimea succesiunii

si mai adaug unu*(unu-1)/2;
si doi*(doi-1)/2;
si afisez...
lucrez in long long
afisez cu %ull
afisez si sfarsit de linie

[•vladcyb1]

Daca imi aduc bine aminte eu nu calculam efectiv panta. Pentru fiecare segment tineam minte din panta numaratorul si numitorul si apoi la soratare faceam produsul mezilor si produsul extremilor ca sa compar si asa evitam kestia cu paralelismul OX sau OY.

[vladut.forum]

pai mai ti-am zis ca nu se pune nici la mine problema de paralelism, eu alea le tin separat, ca e mai simplu...
apoi la panta tin si eu numaratorul si numitroul iar la sortare fac produsul mezilor = produsul extremilor...

[•Cosmin]

Poti sa tii pante ca perechi de numarator numitor, dar fractia tre sa fie ireductibila si atunci doua pante sunt egale cand numaratorii respectiv numitorii sunt egali.

[•Gabi]

Imi puteti spune va rog cat da pt n = 8 ?

Shi punctele:

0 0
1 3
2 0
4 5
3 6
2 7
1 1
4 3

Scuze, am uitat de ele.

[•bogdan2412]

15

[•cristy]

Raspunsul e 24...oricum...traba sa fie par...trebuie numarate de 2 ori trapezele...sunt trapeze in ambele sensuri...

[•bogdan2412]

Am obtinut 15 cu sursa care ia punctaj maxim. Oricum m-am uitat pe datele de intrate si am observat ca 4 5, 3 6, 2 7 sunt puncte coliniare, dar in problema se specifica ca oricare 3 puncte sunt necoliniare.

[•cristy]

Aha...scuze...la asta nu m-am gandit...da...oricum...nu trebuia sa fie numar par?

[u-92]

cum adica le numeri in ambele sensuri? asa numeri de doua ori acelasi trapez.. nu trebuie neaparat ca raspunsul sa fie par

[•cristy]

mah...hash-u asta...defapt inseamna...sa gasesti o formula pt care sa aduni toate pantele la un loc?..si dupa aia aduni...da...trasa sa gasesti o formula ca se la comprimi?...dati ceva exemplu...

[•domino]

mah...hash-u asta...defapt inseamna...sa gasesti o formula pt care sa aduni toate pantele la un loc?..si dupa aia aduni...da...trasa sa gasesti o formula ca se la comprimi?...dati ceva exemplu...

Citeste articolul de hashing de pe http://info.devnet.ro

[•cristy]

ce cazuri particulare sunt aici?...ca iau 70 de pct ca nu ma prind...am facut 1000 de exemple da nu ma prind...iau WA pe 3 teste, 2,7,8...

[•filipb]

Nici eu nu luam testele alea pentru ca foloseam precizie prea mica. Cand am folosit o precizie mare de 10^(-14) luam 100... Mai merge si sa nu faci impartire propriu-zisa, si sa compari fractii inmultind numitorii si numaratorii corespunzatori pe 64 biti si comparand cele doua produse ( asa e si mai exact... )

[•cristy]

eu am facut pur si simplu compararea produsului numitorilor si numaratorilor...da nu pe 64 de biti...pe 32 de biti...oare de aici sa fie problema?...

[•bogdan2412]

Da, cel mai probabil acolo e problema.

[•filipb]

Si vezi ca nu este suficienta numai compararea produsului... De exemplu, 2/(-3) < 2/5, dar 10 > -6...  

[•cristy]

dar de ce conteaza si altceva decat produsul?...eu am facut simplificarile...si daca numitorul era cu minus, inmulteam fractia cu -1, si cat de cat...dupa sortare...erau toate in acelasi loc, adica...valorile probabil nu erau toate in ordine crescatoare...dar macar erau cele egale una langa cealalta...si de aici era usor...