285 Geometry

[•vendetta]

Ia incearca testul asta :

4
-1 -1 1 1
0 -1 0 1
-1 0 1 0
5 5 6 6

afiseaza 4, si ar trebuie sa afiseze 3, deoarece considera ca primul segment se intersecteaza cu ultimul si ele de fapt nu se intersecteaza.

Pentru a-l lua citeste mesajul lui wefgef

majoritatea programelor care nu folosesc respingere rapida pica asemenea teste .

vezi in cormen cu respingerea rapida 

[•Detrol2k]

Ia incearca testul asta :

4
-1 -1 1 1
0 -1 0 1
-1 0 1 0
5 5 6 6

afiseaza 4, si ar trebuie sa afiseze 3, deoarece considera ca primul segment se intersecteaza cu ultimul si ele de fapt nu se intersecteaza.

Pentru a-l lua citeste mesajul lui wefgef

majoritatea programelor care nu folosesc respingere rapida pica asemenea teste .

vezi in cormen cu respingerea rapida 

Ai avut dreptate! A mers! 

[•caliux]

Imi explica si mie cineva in ce consta respingerea rapida si cum ar trebuii implementata?

[•dutzul]

am o intrebare legata de produsul vectorial a 2 vectori am gasit ca e egal cu |a|*|b|*sin(X) unde X e unghiul dintre cele 2 drepte, de aici rezulta ca daca unghiul e intre 90 si 180 atunci produsul e negativ dar totusi sa luam dreapta suport pe axa ox cu originea in O si un punct in cadranul 1 si unu in cadranul 2. atunci un produs da negativ si unul pozitiv dar ambele puncte se afla pe aceiasi parte a dreptei...mersi anticipat 

[•SebiSebi]

Daca este vorba despre drepte atunci doua drepte se intersecteaza daca si numai daca pantele lor difera.
Panta unei drepte determinata de 2 puncte este :
m=(yB-yA) / (xB-xA);

[•SebiSebi]

Fii atent ca in problema se lucreaza cu segmente nu cu drepte.

[•romyk]

imi da si mie cineva un exemplu ca la testul 1 ca sa imi dau seama de ce il tot pic?
folosesc formula de intersectie a doua segmente dar nu imi dau seama de ce nu il iau si pe primul test

[•misino]

Fa testul de respingere rapida.
Asta am facut si eu.

[•romyk]

Nu inteleg ce inseamna "respingere rapida", dar am pus o conditie ca pentru testul:
4
1 1 2 2
3 3 4 4
-1 1 -3 3
3 -3 6 -6
sa imi afiseze 0 si am luat si primul test

[•OviTzu24]

Care ii faza cu "respingerea rapida" ? Am si eu probleme cu testul 1, si nu pricep care ii problema.  
RE : romyk pentru primul test, out = 3 nu 0;

[•romyk]

Nu ziceam de primul test de la evaluator ci de testul care l-am facut eu. Pentru el ar trebui sa afiseze 0. Daca folosesti doar formula de intersectie a segmentelor nu iei acest test(nu am idee de ce). Daca faci pe foaia o sa vezi ca trebuie sa iti dea 0.

[•ion824]

Probabil că ar trebui îmbunătățite testele. Am luat 100 cu sursa care nu verifica cazul în care segmentele ce se intersectau erau coliniare.

[•sstere]

Iau toate testele in afara de Testul 4. Sunt convins ca este corect matematic implementat. Nu stiu ce imi scapa.

[•bciobanu]

Nu m-am uitat foarte atent in sursa ta, dar iti sugerez sa compari numerele reale folosind epsilon.

[•[email protected]]

#include<iostream>
#include<fstream>
using namespace std;
struct element
{
   long long  x1,y1,x2,y2;
};
element v[10000];
int verificare(int i,int j)
{
   int ok=0,a1,a2,b1,b2,c1,c2;
   a1=v.y2-v.y1;
   b1=v.x2*(-1)+v.x1;
   c1=v.y1*v.x2-v.y2*v.x1;
   a2=v[j].y2-v[j].y1;
   b2=v[j].x2*(-1)+v[j].x1;
   c2=v[j].y1*v[j].x2-v[j].y2*v[j].x1;
   if((a1*v[j].x1+b1*v[j].y1+c1)*(a1*v[j].x2+b1*v[j].y2+c1)<=0)
   {
      if((a2*v.x1+b2*v.y1+c2)*(a2*v.x2+b2*v.y2+c2)<=0)
      {
         ok=1;
      }
   }
   return ok;
}
int conditie1(int i,int j)
{
   float n1,n2,ok=0;
   n1=(float)(v.y2-v.y1)/(v.x2-v.x1);
   n2=(float)(v[j].y2-v[j].y1)/(v[j].x2-v[j].x1);
   if(n1!=n2)
   {
      ok=1;
   }
   return ok;
}
   
   
int main()
{
   
   long long n,i,j,nr=0;
   fstream f("geometry.in",ios::in);
   f>>n;
   for(i=1;i<=n;i++)
   {
      f>>v.x1>>v.y1>>v.x2>>v.y2;
   }
   f.close();
   for(i=1;i<n;i++)
   {
      for(j=i+1;j<=n;j++)
      {
         if(conditie1(i,j)==1)
         {
         if(verificare(i,j)==1)
         {
            nr++;
         }
         }
      }
      
   }
   fstream g("geometry.out",ios::out);
   g<<nr;
   g.close();
}

[•[email protected]]

o solutie de 100 puncte

[•[email protected]]

o solutie de 100