Pagini: [1] 2   În jos
  Imprimă  
Ajutor Subiect: 285 Geometry  (Citit de 13903 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
ditzone
Vizitator
« : Octombrie 15, 2006, 21:30:02 »

Aici puteţi discuta despre problema Geometry.
Memorat
rmikeweb
Strain


Karma: -4
Deconectat Deconectat

Mesaje: 20



Vezi Profilul
« Răspunde #1 : Octombrie 17, 2006, 12:38:58 »

Poate sa-mi explice si mie cineva ce e gresit in urmatoarea sursa. Am luat in considerare toate cazurile cand segmentele se intersecteaza is paralele sau segmentele is pe aceasi dreapta si iau doar 20p?? Read This!
Cod:
const fis='geometry';
      nmax=500;
var x1,x2,y1,y2,a,b,c:array[1..nmax] of longint;
    n,rez:longint;

Procedure read_data;
var i:longint;
begin
readln(n);
for i:=1 to n do
    begin
    readln(x1[i],y1[i],x2[i],y2[i]);
    a[i]:=y2[i]-y1[i];
    b[i]:=x2[i]-x1[i];
    c[i]:=(x1[i]*y2[i])-(x2[i]*y1[i]);
    end;
end;

Procedure compute;
var i,j:longint;
    y:real;

Function peg(n1,n2:longint):boolean;
begin
if a[n1]*b[n2]=a[n2]*b[n1]
then peg:=true
else peg:=false;
end;

Function ini(aa,bb:longint;c:real):boolean;
var a,b:longint;
begin
if aa<=bb
then begin
     a:=aa;
     b:=bb;
     end
else begin
     a:=bb;
     b:=aa;
     end;
if (a<=c) and (c<=b)
then ini:=true
else ini:=false;
end;

begin
for i:=2 to n do
    for j:=1 to i-1 do
        if peg(i,j)
        then begin
             if (c[i]=c[j]) and (ini(x1[i],x2[i],x1[j]) or
             ini(x1[i],x2[i],x2[j]) or ini(x1[j],x2[j],x1[i]) or ini(x1[j],x2[j],x2[i]))
             then inc(rez);
             end
        else begin
             y:=((c[j]*a[i])-(c[i]*a[j]))/((b[i]*a[j])-(b[j]*a[i]));
             if ini(y1[i],y2[i],y) and ini(y1[j],y2[j],y)
             then inc(rez);
             end;
end;

begin
assign(input,fis+'.in');
reset(input);
assign(output,fis+'.out');
rewrite(output);
read_data;
compute;
writeln(rez);
close(output);
close(input);
end.
Memorat

Mike
u-92
Vizitator
« Răspunde #2 : Octombrie 17, 2006, 13:51:19 »

nu inteleg ce faci tu.. dar iti sugerez sa incerci cu produs incrucisat, cred ca e cel mai comod. AB se intersecteaza cu CD daca (A, C, B) * (A, D, B) <= 0 si (D, A, C) * (D, B, C) <= 0

unde (A, B, C) = AB x AC
Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #3 : Octombrie 28, 2006, 15:37:00 »

nu vreau sa insinuez nimik doar ca fapt divers eu am luat 100 de pct cu un program care ptr testul:

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.

PS : folosesc ecuatia dreptei
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #4 : Octombrie 28, 2006, 16:46:16 »

majoritatea programelor care nu folosesc respingere rapida pica asemenea teste Tongue.

vezi in cormen cu respingerea rapida  peacefingers
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
peanutz
Nu mai tace
*****

Karma: 10
Deconectat Deconectat

Mesaje: 296



Vezi Profilul
« Răspunde #5 : Iunie 06, 2007, 15:59:24 »

Este un 3 in plus pe prima linie in exemplu.

L.E.: acum e ok Tongue
« Ultima modificare: Iunie 07, 2007, 13:47:55 de către Andrei Homorodean » Memorat

....staind....
bent_larsen
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 18



Vezi Profilul
« Răspunde #6 : Septembrie 22, 2007, 21:34:05 »

Poate sa-mi zica si mie cineva ce au asa special testele de la 5 in sus ca mai mult de 40 de puncte nu iau
desi fac cu produs incrucisat si respingere rapida Brick wall
Memorat
fireatmyself
Nu mai tace
*****

Karma: 36
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #7 : Septembrie 23, 2007, 22:02:20 »

iei tle sau wa? (testele nu au nimic special)
Memorat

Viata e scurta. Daca nu o putem lungi, macar s-o facem lata.
bent_larsen
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 18



Vezi Profilul
« Răspunde #8 : Septembrie 24, 2007, 12:25:01 »

Iau WA si nu-mi dau seama ce gresesc,fac exact cum zice in Cormen.Gresesc undeva?
Memorat
coderninu
Strain
*

Karma: 1
Deconectat Deconectat

Mesaje: 26



Vezi Profilul
« Răspunde #9 : Septembrie 25, 2007, 22:23:59 »

Eu am testat intersectia a 2 seg cu arii si cu respingere rapida.prima data facem respingerea apoi am calculat aria cu semn a unui triunghi format din primul segment si un punct din al doilea segment si aria triunghiului format din acelasi segment(adik primu`) cu al doilea punct.Daca aveau acelasi semn segmentele nu se puteau intersecta.Apoi am luat cel de-al doilea segment si cu punctele care formau primul segment si calculam ariile si din nou  daca aveau ac semn , seg nu se intersectau.daca trecea de testele acestea, inseamna ca segmentele se intersectau.Nu trebe neaparat aria, ideea era ca punctele sa fie de cele 2 parti ale segmentului, dar mie mi s-a parut mai usor sa explic folosind arii, dar merge la fel ed bine cu produs incrucisat.
Si am luat doua "for", daca seg i se inters cu seg j incrementam rezultatul.
Si am luat 100  Very Happy peacefingers Yahoo!

Poate va ajuta ideea asta  wink
Memorat
ssergiuss
Strain


Karma: 41
Deconectat Deconectat

Mesaje: 24



Vezi Profilul
« Răspunde #10 : Martie 29, 2009, 00:53:06 »

Imi poate spune cineva conditia de intersectie a doua segmente sau unde o pot gasi. Daca nu se poate pe forum macar mesaj privat. I'as fi recunoscator celui ce m'ar ajuta.
Memorat
sima_cotizo
Nu mai tace
*****

Karma: 219
Deconectat Deconectat

Mesaje: 596



Vezi Profilul
« Răspunde #11 : Martie 29, 2009, 01:09:26 »

Daca ai segmentele [AB] si [CD], trebuie sa ai conditiile A si B de o parte si de cealalta a dreptei CD si C si D de o parte si de cealalta a dreptei AB. Cu alte cuvinte, cand introduci punctele A si B in ecuatiile dreptei CD, produsul rezultatelor trebuie sa fie negativ (si analog pt celalalt caz).
Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #12 : Martie 29, 2009, 08:54:42 »

Aici gasesti tutorialu de geometrie de pe topcoder. Poti face intersectia dreptelor suport ale segmentelor, iar apoi verifici daca punctu de intersectia apartine ambelor segmente
Memorat
ssergiuss
Strain


Karma: 41
Deconectat Deconectat

Mesaje: 24



Vezi Profilul
« Răspunde #13 : Martie 29, 2009, 11:49:45 »

Va multumesc mult! Am reusit sa iau 100  Yahoo!.
Memorat
geniucos
Vorbaret
****

Karma: 21
Deconectat Deconectat

Mesaje: 199



Vezi Profilul
« Răspunde #14 : Mai 28, 2012, 12:03:51 »

Ma poate ajuta si pe mine cineva?Sa imi dea un test mai mare sau sa-mi zica unde am gresit ca nu imi merg decat testele 1,2 si 4 si nu gasesc nici o greseala

Cod:
#include<cstdio>
using namespace std;
int n,nr,i,j,a[3],b[3],c[3],x1[502],x2[502],y1[502],y2[502];
double m[503];
double av,bv,eps;
double abs(double val)
{
if(val<0) return val*-1;
return val;
}
void detec(int x1,int y1,int x2,int y2,int p)
{
a[p]=y1-y2;
b[p]=x2-x1;
c[p]=x1*y2-y1*x2;
}
void inter(int a1,int b1,int a2,int b2,int x1,int y1,int x2,int y2)
{
detec(a1,b1,a2,b2,1);
detec(x1,y1,x2,y2,2);
bv=double(c[2]*a[1]-c[1]*a[2])/(b[1]*a[2]-b[2]*a[1]);
av=double(-b[1]*bv-c[1])/a[1];
}
int ap(int x1,int y1,int x2,int y2,double a2,double b2)
{
if((a2>=x1&&a2<=x2)||(a2<=x1&&a2>=x2)) ;
else return 0;
if((b2>=y1&&b2<=y2)||(b2<=y1&&b2>=y2)) ;
else return 0;
return 1;
}
int main()
{
freopen("geometry.in","r",stdin);
freopen("geometry.out","w",stdout);
scanf("%d",&n);
eps=0.0001;
for(i=1;i<=n;i++)
{
scanf("%d",&x1[i]);
scanf("%d",&y1[i]);
scanf("%d",&x2[i]);
scanf("%d",&y2[i]);
if(x2[i]!=x1[i]) m[i]=(double)(y2[i]-y1[i])/(x2[i]-x1[i]);
else m[i]=-1;
}
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
{
if((double)abs((double)m[i]-m[j])>eps)
{
inter(x1[i],y1[i],x2[i],y2[i],x1[j],y1[j],x2[j],y2[j]);
if(ap(x1[i],y1[i],x2[i],y2[i],av,bv)==1&&ap(x1[j],y1[j],x2[j],y2[j],av,bv)==1) nr++;
}
else
//{
//detec(x1[i],y1[i],x2[i],y2[i],1);
if(ap(x1[i],y1[i],x2[i],y2[i],x1[j],y1[j])==1||ap(x1[i],y1[i],x2[i],y2[i],x2[j],y2[j])==1) nr++;
//}
}
printf("%d\n",nr);
return 0;
}
« Ultima modificare: Mai 28, 2012, 13:15:16 de către Andrei Grigorean » Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #15 : Iunie 19, 2012, 16:05:25 »

Am gasit ceva interesant despre algoritmi si probleme de geometrie computationala aici :
http://campion.edu.ro/arhiva/index.php?page=paper&action=view&id=41
Sper sa fie de folos.
Memorat
vendetta
De-al casei
***

Karma: 72
Deconectat Deconectat

Mesaje: 122



Vezi Profilul
« Răspunde #16 : Octombrie 15, 2012, 17:28:06 »

Salut! Iau incorect pe primul test si nu ma prind de ce.
Solutia mea e cam asa : iau fiecare pereche de 2 segmente si vad daca se intersecteaza;
Verific daca doua segmente se intersecteaza astfel : iau un segment si vad daca punctele care determine celalalt segment se afla in semiplane opuse fata de segmentul ales.

L.E. : Mi-a iesit pana la urma.
« Ultima modificare: Octombrie 15, 2012, 19:56:18 de către Salajan Razvan » Memorat
misino
Strain
*

Karma: 10
Deconectat Deconectat

Mesaje: 40



Vezi Profilul
« Răspunde #17 : Octombrie 25, 2012, 20:38:49 »

Imi poate spune si mie cineva ce gresesc la problema aceasta?
Iau ok doar pe  3 teste.
Cod:
#include<algorithm>
#include<fstream>
using namespace std;
ifstream f("geometry.in");
ofstream g("geometry.out");
int i,e,j,n,nr,ok,v[200];
struct pc{int x,y;};
pc a[510],b[510];
int s(pc a,pc b,pc c)
{
    return a.y*(c.x-b.x)-a.x*(c.y-b.y)+b.x*c.y-c.x*b.y;
}
int inter(pc a1,pc b1,pc a2,pc b2)
{
    return (s(a2,a1,b1)*s(b2,a1,b1)<=0&&s(a1,a2,b2)*s(b1,a2,b2)<=0);
}
int main()
{
    f>>n;
    for(i=1;i<=n;++i)
    {
        f>>a[i].x>>a[i].y>>b[i].x>>b[i].y;
    }
    for(i=1;i<=n;++i)
    for(j=i+1;j<=n;++j)
    if(inter(a[i],b[i],a[j],b[j]))
    ++nr;
    g<<nr<<'\n';
    return 0;
}
Memorat
lucian666
Client obisnuit
**

Karma: 16
Deconectat Deconectat

Mesaje: 84



Vezi Profilul
« Răspunde #18 : Octombrie 26, 2012, 22:21:58 »

 Buna seara  Smile .AM folosit la problema asta o metoda cu determinanti(sarrus) insa nu iau decat 3 teste Cry

Sunt atent la toate atribuirile,variabilele sunt toate de tip double ,nu stiu de ce nu merge Brick wall

Vreo sugestie ceva?
Multumesc  Smile

L.E  Very Happy variabilele nu erau toate de tip double,dupa ce le-am facut de tip double iau 50 pct cu Incorrect doar pe 1 test...
L.E2

Imi poate spune si mie cineva ce gresesc la problema aceasta?
Iau ok doar pe  3 teste.



Onisim pune in structura double la x si y ,iar functia aia s cred ca trebuie sa fie de tip double  Confused

O seara placuta!!!
« Ultima modificare: Octombrie 26, 2012, 22:47:11 de către Vasilut Lucian » Memorat
misino
Strain
*

Karma: 10
Deconectat Deconectat

Mesaje: 40



Vezi Profilul
« Răspunde #19 : Octombrie 27, 2012, 16:11:28 »

ms o sa incerc!!
Memorat
misino
Strain
*

Karma: 10
Deconectat Deconectat

Mesaje: 40



Vezi Profilul
« Răspunde #20 : Octombrie 30, 2012, 10:00:52 »

am modificat si tot 0 pct
;
 Read This!
Cod:
#include<algorithm>
#include<fstream>
using namespace std;
ifstream f("geometry.in");
ofstream g("geometry.out");
int i,e,j,n,nr,ok,v[200];
struct pc{double x,y;};
pc a[510],b[510];
double s(pc a,pc b,pc c)
{
    return a.y*(c.x-b.x)-a.x*(c.y-b.y)+b.x*c.y-c.x*b.y;
}
double inter(pc a1,pc b1,pc a2,pc b2)
{
    return (s(a2,a1,b1)*s(b2,a1,b1)<=0&&s(a1,a2,b2)*s(b1,a2,b2)<=0);
}
int main()
{
    f>>n;
    for(i=1;i<=n;++i)
    {
        f>>a[i].x>>a[i].y>>b[i].x>>b[i].y;
    }
    for(i=1;i<=n;++i)
    for(j=i+1;j<=n;++j)
    if(inter(a[i],b[i],a[j],b[j]))
    ++nr    g<<nr<<'\n';
    return 0;
}
Angry
Memorat
lucian666
Client obisnuit
**

Karma: 16
Deconectat Deconectat

Mesaje: 84



Vezi Profilul
« Răspunde #21 : Noiembrie 01, 2012, 13:04:39 »

 Smile Salut.Ce are mai special testul 1 ? doar pe el iau incorrect  Brick wall
Memorat
Detrol2k
Strain
*

Karma: -2
Deconectat Deconectat

Mesaje: 48



Vezi Profilul
« Răspunde #22 : Noiembrie 09, 2012, 14:53:47 »

Si eu m-am blocat la primul test. Un hint ar fi foarte apreciat!  Cry
Memorat
repp4radu
Nu mai tace
*****

Karma: 118
Deconectat Deconectat

Mesaje: 204



Vezi Profilul
« Răspunde #23 : Noiembrie 09, 2012, 18:58:11 »

Pentru cei care picati primul test, aveti grija cand determinati punctul de intersectie sa faceti coordonatele ca lumea. Eu acolo greseam.

Incercati testul asta:
Cod:
3
0 -2 0 2
0 0 2 0
0 3 2 0

Raspuns: 2
Memorat
Detrol2k
Strain
*

Karma: -2
Deconectat Deconectat

Mesaje: 48



Vezi Profilul
« Răspunde #24 : Noiembrie 09, 2012, 19:55:27 »

Pentru cei care picati primul test, aveti grija cand determinati punctul de intersectie sa faceti coordonatele ca lumea. Eu acolo greseam.

Incercati testul asta:
Cod:
3
0 -2 0 2
0 0 2 0
0 3 2 0

Raspuns: 2

Imi da bine pe testul tau! Si totusi pic testul 1.  Cry
Memorat
Pagini: [1] 2   În sus
  Imprimă  
 
Schimbă forumul:  

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