047 Trapez

[nivan]

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;
 }

[nivan]

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)

[ditzone]

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

[•svalentin]

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

[•Coty]

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:

[•marcelcodrea]

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. 

Multumesc anticipat !   

[•tm_radu]

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.

[•marcelcodrea]

am reusit sa iau 100  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 ?

[•filipb]

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

[•marcelcodrea]

Merci pentru informatie!!!

[•gabitzish1]

imi da cineva o idee cum sa sortez dupa panta fara sa fac impartirea y/x ?

[•peanutz]

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

[•devilkind]

pai poti compara 2 fractii aducandule la acelasi numitor. Banuiesc ca dak stii sa le compari vei putea face si sortarea.

[•nash]

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

[•cos_min]

Uite aici unu:

Cod:

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

Cod:

10

[•mihai_florea]

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

[•Mishu91]

Oricare trei puncte sunt necoliniare

Printre alea tu ai trei puncte coliniare((1 2), (1 4), (1 5))  probabil de aia obtineti rezultate diferite.

[•Oancea.Catalin]

dati-mi si mie niste teste va rog... iau wA pe 8 teste ( si pe celelate 2 teste iau TLE  )

[•Bit_Master]

Punctele se pot repeta? (cred ca nu)

[•gerd13]

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 ?