285 Geometry

[ditzone]

Aici puteţi discuta despre problema Geometry.

[•rmikeweb]

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

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.

[u-92]

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

[•devilkind]

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

[•wefgef]

majoritatea programelor care nu folosesc respingere rapida pica asemenea teste .

vezi in cormen cu respingerea rapida 

[•peanutz]

Este un 3 in plus pe prima linie in exemplu.

L.E.: acum e ok

[•bent_larsen]

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

[•fireatmyself]

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

[•bent_larsen]

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

[•coderninu]

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 

Poate va ajuta ideea asta 

[•ssergiuss]

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.

[•sima_cotizo]

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

[•Mishu91]

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

[•ssergiuss]

Va multumesc mult! Am reusit sa iau 100  .

[•geniucos]

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

[•SebiSebi]

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.

[•vendetta]

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.

[•misino]

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

[•lucian666]

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

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

Vreo sugestie ceva?
Multumesc  

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

O seara placuta!!!

[•misino]

ms o sa incerc!!

[•misino]

am modificat si tot 0 pct
;
 

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

[•lucian666]

  Salut.Ce are mai special testul 1 ? doar pe el iau incorrect 

[•Detrol2k]

Si eu m-am blocat la primul test. Un hint ar fi foarte apreciat! 

[•repp4radu]

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

[•Detrol2k]

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.