Pagini: 1 [2]   În jos
  Imprimă  
Ajutor Subiect: 047 Trapez  (Citit de 13088 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
nivan
Vizitator
« Răspunde #25 : Noiembrie 08, 2005, 17:51:37 »

Este explicabil de ce iese din timp.
Ma gandesc ca as mai putea pune niste conditii la punctele de le aleg cand calcyulez panta astfel incat sa reduc la mai putine puncte shi sa pot sa parcurc ulteror vectorul cu pante sa intre in timp. Sper k ma puteti ajuta.
Cod:
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

long i,j,n,m,trap;
float a[1000000],x[1001],y[1001];

void quick(long li, long ls)
{
 long i,j; float x,y;
 i=li; j=ls; x=a[(li+ls)/2];
 while (i<=j)
      {
       while (a[i]>x) i++;
       while (a[j]<x) j--;
       if (i<=j)
{
 y=a[i]; a[i]=a[j]; a[j]=y;
 i++; j--;
}
      }
 if (i<ls) quick(i,ls);
 if (j>li) quick(li,j);
}

int main()
{
 FILE *f=fopen("trapez.in","r");
 fscanf(f,"%ld",&n);
 for (i=1;i<=n;i++)
    fscanf(f,"%ld%ld",&x[i],&y[i]);
 fclose(f);

 long h=0;
 printf("\n");

 for (i=1;i<=n-1;i++)
 for (j=i+1;j<=n;j++)
    if (i != j)
      {
       h++;
       if (x[j]-x[i] == 0)
a[h]=0;
else if (y[j]-y[i] == 0)
a[h]=2500000000;
else a[h]=(y[j]-y[i])/(x[j]-x[i]);
       printf("%ld %ld %f\n",i,j,a[h]);
      }

 quick(1,h);
 trap=0;
 for (i=1;i<=h-1;i++)
    if (a[i]==a[i+1])
      trap++;

 FILE *g=fopen("trapez.out","w");
 fprintf(g,"%ld",trap);
 fclose(g);
 return 0;
 }
Memorat
nivan
Vizitator
« Răspunde #26 : Noiembrie 10, 2005, 12:31:33 »

Gata am rezolvat problema cu faptul ca iesea din timp..... eram eu idiot shi imi ramasese ceva printat pe ecran  eh...dar nu asta e problema acuma imi da WA pe testele pe care imi dadea atuncea TLE. Cumva nu trebuie sa calculez panta pe reale, ca am citit prin probleme ca se creeaza erori de precizie (dar daca nu merge pe reale.... pei pe ce pot stoca panta cre este practic un raport)
Memorat
ditzone
Vizitator
« Răspunde #27 : Noiembrie 10, 2005, 15:06:54 »

Inainte sa postezi ceva citeste cu atentie ce s-a mai discutat la acel topic.. deoarece poate exista raspunsul la intrebarea ta deja... cum de altfel e si in cazul de fata....
Memorat
svalentin
Nu mai tace
*****

Karma: 88
Deconectat Deconectat

Mesaje: 704



Vezi Profilul
« Răspunde #28 : Noiembrie 16, 2005, 16:43:28 »

pentru cei care faceti calcule pe reale in C, la calcularea pantei, puteti sa folositi atan2(y,x)!
atan2 este o functie care returneaza unghiul in radianti si este corecta si in cazurile de paralelism cu axele! Dar atentie, repet, ea returneaza unghiul dintre 2 puncte, NU panta; pentru aflarea pantei mai trebuie facut un calcul
Memorat
Coty
Nu mai tace
*****

Karma: 6
Deconectat Deconectat

Mesaje: 235



Vezi Profilul WWW
« Răspunde #29 : Decembrie 28, 2005, 16:11:33 »

Citat din mesajul lui: 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...


si eu am luat produsul, am sortat, am tinut seama de schema cu -1... si tot iau WA la testele 2,7,8 ... si sigur evaluarea unei expresii o face pe 64 de biti in FPC... ce are? exista raspunsuri care ies din int64?  :cry:
Memorat
marcelcodrea
Nu mai tace
*****

Karma: 173
Deconectat Deconectat

Mesaje: 217



Vezi Profilul
« Răspunde #30 : Iunie 29, 2006, 16:47:54 »

Stie cineva daca se poate evita lucrul pe 64 biti aducand fractiile pantelor la o forma ireductibila si dupa aceea ordonand cu qsort dupa numarator(unde numaratorul este egal dupa numitor) si adunand la rezultat nr*(nr-1)/2 unde nr reprezinta numarul de rapoarte consecutive egale(numarator=numitor)?Sursa imi ia 60 p(restul WA) si as vrea sa stiu daca este de vina rationamentul sau am gresit la implementare!
Am tinut cont de dreptele paralele cu axele si am mutat "-" sus pentru a evita cazurile in care -2/4 si 2/-4  nu sunt consecutive in urma ordonarii!!!

P.S.  Brick wall

Multumesc anticipat !    Very Happy
Memorat
tm_radu
De-al casei
***

Karma: 16
Deconectat Deconectat

Mesaje: 140



Vezi Profilul
« Răspunde #31 : Iunie 29, 2006, 17:58:15 »

Rationamentul este bun, la implementare e buba. Vezi daca nu ai implementat gresit qsort-ul sau descompunerea in fractii ireductibile. Poti incerca si metoda in care tii fiecare raport nu ca numitor si numarator, ci direct ca numar real, numai sa ai grija cand verifici egalitatea.
Memorat

Daca nu merge o preblema, depaneaz-o, si abia apoi arunci calculatoru pe geam
marcelcodrea
Nu mai tace
*****

Karma: 173
Deconectat Deconectat

Mesaje: 217



Vezi Profilul
« Răspunde #32 : Iunie 30, 2006, 10:57:12 »

am reusit sa iau 100  Winner 3rd place pana la urma...era o greseala la implementare pe la linia 117 si mi-a luat ceva vreme;oricum nu stiti unde as putea sa aflu ceva despre numerele pe 64 biti,ca nu am gasit articol si nici la scoala nu am invatat despre asa ceva ?
Memorat
filipb
Nu mai tace
*****

Karma: 232
Deconectat Deconectat

Mesaje: 929



Vezi Profilul
« Răspunde #33 : Iunie 30, 2006, 11:08:26 »

"Numerele pe 64 de biti" este acelasi lucru ca si numerele pe "32 de biti" ( adica long / int sub Linux ) sau " 16 biti " ( int sub Windows ). In C/C++ declari pur si simplu "long long a" ( variabila a este de 64 de biti ), iar in Pascal "var a:int64". 64 de biti inseamna ca un bit este ocupat de semn, iar restul de cate o cifra in baza 2 ( 0 sau 1 ). Astfel, numarul maxim pe 64 de biti este 111..1111 - unde 1 apare de 63 de ori ( pentru ca al 64-lea bit este alocat pentru semn, + sau - ), deci valoarea maxima este 2^63 - 1... Atata tot, cu precizarea ca poti folosi exact aceleasi operatii ca si pentru numerele pe 16 / 32 biti...   
Memorat
marcelcodrea
Nu mai tace
*****

Karma: 173
Deconectat Deconectat

Mesaje: 217



Vezi Profilul
« Răspunde #34 : Iunie 30, 2006, 12:24:59 »

Merci pentru informatie!!! peacefingers
Memorat
gabitzish1
Moderatori infoarena
Nu mai tace
*****

Karma: 321
Deconectat Deconectat

Mesaje: 926



Vezi Profilul
« Răspunde #35 : August 13, 2007, 11:59:21 »

imi da cineva o idee cum sa sortez dupa panta fara sa fac impartirea y/x ?
Memorat
peanutz
Nu mai tace
*****

Karma: 10
Deconectat Deconectat

Mesaje: 296



Vezi Profilul
« Răspunde #36 : August 13, 2007, 12:22:24 »

Eu m-am chinuit sa fac sortarea fara impartire si nu mi-a iesit. Am schimbat in impartire si a mers din prima, dar vezi sa folosesti ceva precizie..
Memorat

....staind....
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #37 : August 13, 2007, 12:23:17 »

pai poti compara 2 fractii aducandule la acelasi numitor. Banuiesc ca dak stii sa le compari vei putea face si sortarea.
Memorat
nash
De-al casei
***

Karma: 0
Deconectat Deconectat

Mesaje: 109



Vezi Profilul
« Răspunde #38 : Martie 12, 2008, 23:06:15 »

Ok ... problema asta este simpla .. insa .. nu stiu de ce nu iau decat 0 ... poate sa imi dea cineva un test ca la mine merge pe toate ....
Memorat
cos_min
Nu mai tace
*****

Karma: 48
Deconectat Deconectat

Mesaje: 493


live


Vezi Profilul
« Răspunde #39 : Martie 13, 2008, 09:43:58 »

Uite aici unu:

Cod:
7
1 5
3 5
1 2
1 4
3 7
2 4
2 6

Cod:
10
Memorat

vid...
mihai_florea
Strain


Karma: 17
Deconectat Deconectat

Mesaje: 24



Vezi Profilul
« Răspunde #40 : Aprilie 11, 2008, 20:46:09 »

Uite aici unu:

Cod:
7
1 5
3 5
1 2
1 4
3 7
2 4
2 6

Cod:
10


pentru testu' asta mie imi da
Cod:
14

cu sursa pe care am luat 100 de pct
Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #41 : Aprilie 11, 2008, 22:28:10 »

Citat
Oricare trei puncte sunt necoliniare

Printre alea tu ai trei puncte coliniare((1 2), (1 4), (1 5))  probabil de aia obtineti rezultate diferite.
« Ultima modificare: Aprilie 11, 2008, 23:05:04 de către Andrei Misarca » Memorat
Oancea.Catalin
Client obisnuit
**

Karma: -3
Deconectat Deconectat

Mesaje: 75



Vezi Profilul
« Răspunde #42 : Decembrie 26, 2010, 18:23:43 »

dati-mi si mie niste teste va rog... iau wA pe 8 teste ( si pe celelate 2 teste iau TLE  Rolling on the Floor Laughing )
Memorat
Bit_Master
Vorbaret
****

Karma: -49
Deconectat Deconectat

Mesaje: 159



Vezi Profilul
« Răspunde #43 : Februarie 07, 2011, 21:34:13 »

Punctele se pot repeta? (cred ca nu)
Memorat
gerd13
Strain


Karma: -2
Deconectat Deconectat

Mesaje: 14



Vezi Profilul
« Răspunde #44 : Noiembrie 05, 2014, 23:48:13 »

Contactează autorul problemei:
Evaluatorul nu a returnat un număr la stdout pe testul 1 (se ignoră spaţii, newline, etc)


Ciudat, numai exista fisiere in ?
Memorat
Pagini: 1 [2]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines