191 - Intersection

[paulhryu]

Two things you never do with floats and doubles:

1. Compare them directly.
2. Converting them directly to integers.

You suffer from the first problem. NEVER compare floats directly. Due to rounding errors, you may have minute differences that make the internal representations different.

Instead of a == b, use fabs(a - b) < ERROR, for which ERROR = .00000001 or some other small, but not too small, number. If you don't want to use fabs, then here's a macro for you to use:

#define ERROR .00000001
#define float_equals(a,b) (a - b < ERROR && b - a < ERROR)

The same applies to greater than and less than.

#define float_isless(a, b) (b - a > ERROR)

Now, the other part of your code. I don't feel like going through it. It's probably the right algorithm. But on these computational geometry problems, you can never go wrong with premanufactured algorithms. They will save you time, and though these algebraic solutions are great, the problem is they often have little exceptions and such.

For a great source of those precanned geometry algorithms, go to http://www.softsurfer.com which has excellent solutions for convex hulls, intersections, area, inclusion in polygon (very useful), you name it.

In this case, divide the rectangle into four lines and do intersections for each. Believe me, this works a lot better than solving equations with algebra and you'll get more accepted this way.

But do correct your program to account for rounding errors.

[Cool Guyz]

thx, i already found the mistakes
but it will try ur way too
look like it can be more simple
than my solution
thx again

[Riyad]

[c]

i dont find any prob with my algorithm and cant find any problem with my code, pliiiiiiiiiiiiizzzzzzzzzz help. here is my code

Code: Select all

#include<stdio.h>

struct point {
	long int x,y;

}a,b,c,d,e,f;

#define max(a,b) ((a)>(b)? (a): (b))
#define min(a,b) ((a)>(b)? (b):(a))

int direction(struct point pi,struct point pj,struct point pk){

	return ((pk.x-pi.x)*(pj.y-pi.y)-(pj.x-pi.x)*(pk.y-pi.y));

} 

int on_segment(struct point pi,struct point pj,struct point pk){

	
	if((max(pi.x,pj.x)>=pk.x && pk.x>= min(pi.x,pj.x))&&(max(pi.y,pj.y)>=pk.y&& pk.y>=min(pi.y,pj.y)))
		return 1;
	else
		return 0;

}

int intersect(struct point p1,struct point p2,struct point p3,struct point p4){

	long int d1,d2,d3,d4;
	d1=direction(p3,p4,p1);
	d2=direction(p3,p4,p2);
	d3=direction(p1,p2,p3);
	d4=direction(p1,p2,p4);

	if(((d1>0&& d2<0)|| (d1<0&&d2>0)) && ((d3>0&&d4<0)||(d3<0&&d4>0)))
		return 1;
	else if(d1==0 && on_segment(p3,p4,p1))
		return 1;
	else if(d2==0 && on_segment(p3,p4,p2))
		return 1;
	else if(d3==0 && on_segment(p1,p2,p3))
		return 1;
	else if(d4==0 && on_segment(p1,p2,p4))
		return 1;
	else
		return 0;


}
int main(){

	long int cases;
	long int xl,xr,yt,yb;
	long int xs,ys,xe,ye;
	int flag1,flag2,flag3,flag4;
	freopen("input.in","rt",stdin);
	freopen("E:\out.txt","wt",stdout);
	scanf("%ld",&cases);
	
	while(cases>0){
	
		scanf("%ld %ld %ld %ld %ld %ld %ld %ld",&xs,&ys,&xe,&ye,&xl,&yt,&xr,&yb);

		a.x=xl;a.y=yt;
		c.x=xr;c.y=yb;
		b.x=xr;b.y=yt;
		d.x=xl;d.y=yb;
		e.x=xs;e.y=ys;
		f.x=xe;f.y=ye;

		flag1=intersect(a,b,e,f);
		flag2=intersect(b,c,e,f);
		flag3=intersect(c,d,e,f);
		flag4=intersect(d,a,e,f);

		if(flag1==0&& flag2==0 && flag3==0 && flag4==0){
			printf("F\n");
		}
		else if(flag1==1||flag2==1||flag3==1||flag4==1){
			printf("T\n");
		}
	
		cases--;	
	
	}
	
	return 0;
}

thanx in advance
Riyad

[/c]

[UFP2161]

The line is said to intersect the rectangle if the line and the rectangle have at least one point in common. The rectangle consists of four straight lines and the area in between. Although all input values are integer numbers, valid intersection points do not have to lay on the integer grid.

[Joseph Kurniawan]

There's a sample I/O available in page 5 written ( the Author is haquin) in this Volume. Try with those, maybe they will help.

[Joseph Kurniawan]

Here's the sample input

Code: Select all

68 
4 9 11 2 1 1 7 5 
11 2 4 9 1 1 7 5 
12 12 24 24 19 5 25 17 
4 6 15 9 1 1 11 11 
19 5 25 17 12 12 24 24 
0 18 8 12 1 1 11 11 
2 4 4 2 1 1 11 11 
-4 9 -11 2 -1 1 -7 5 
-11 2 -4 9 -1 1 -7 5 
-12 12 -24 24 -19 5 -25 17 
-4 6 -15 9 -1 1 -11 11 
-19 5 -25 17 -12 12 -24 24 
0 18 -8 12 -1 1 -11 11 
-2 4 -4 2 -1 1 -11 11 
4 -9 11 -2 1 -1 7 -5 
11 -2 4 -9 1 -1 7 -5 
12 -12 24 -24 19 -5 25 -17 
4 -6 15 -9 1 -1 11 -11 
19 -5 25 -17 12 -12 24 -24 
0 -18 8 -12 1 -1 11 -11 
2 -4 4 -2 1 -1 11 -11 
-4 -9 -11 -2 -1 -1 -7 -5 
-11 -2 -4 -9 -1 -1 -7 -5 
-12 -12 -24 -24 -19 -5 -25 -17 
-4 -6 -15 -9 -1 -1 -11 -11 
-19 -5 -25 -17 -12 -12 -24 -24 
0 -18 -8 -12 -1 -1 -11 -11 
-2 -4 -4 -2 -1 -1 -11 -11 
9 1 9 2 4 3 9 6 
9 2 9 1 4 3 9 6 
10 3 13 3 4 3 9 6 
13 3 10 3 4 3 9 6 
10 6 14 6 4 3 9 6 
14 6 10 6 4 3 9 6 
9 7 9 10 4 3 9 6 
9 10 9 7 4 3 9 6 
4 7 4 10 4 3 9 6 
4 10 4 7 4 3 9 6 
0 6 3 6 4 3 9 6 
3 6 0 6 4 3 9 6 
1 3 3 3 4 3 9 6 
3 3 1 3 4 3 9 6 
4 0 4 2 4 3 9 6 
4 2 4 0 4 3 9 6 
5 3 8 5 4 3 9 6 
8 5 5 3 4 3 9 6 
5 3 8 3 4 3 9 6 
8 3 5 3 4 3 9 6 
6 4 6 5 4 3 9 6 
6 5 6 4 4 3 9 6 
4 3 9 6 4 3 9 6 
9 6 4 3 4 3 9 6 
4 3 5 4 4 3 9 6 
5 4 4 3 4 3 9 6 
5 3 8 3 4 3 9 6 
8 3 5 3 4 3 9 6 
5 3 9 3 4 3 9 6 
9 3 5 3 4 3 9 6 
4 4 4 5 4 3 9 6 
4 5 4 4 4 3 9 6 
4 3 4 5 4 3 9 6 
4 5 4 3 4 3 9 6 
4 3 4 6 4 3 9 6 
4 6 4 3 4 3 9 6 
9 2 9 5 4 3 9 6 
9 5 9 2 4 3 9 6 
9 2 9 7 4 3 9 6 
9 7 9 2 4 3 9 6

And the Output will be

Code: Select all

F 
F 
F 
T 
T 
F 
T 
F 
F 
F 
T 
T 
F 
T 
F 
F 
F 
T 
T 
F 
T 
F 
F 
F 
T 
T 
F 
T 
F 
F 
F 
F 
F 
F 
F 
F 
F 
F 
F 
F 
F 
F 
F 
F 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 

[Almost Human]

I am having problem on this and am looking for your help.

I couldn't figure out why for this input :

2 4 4 2 1 1 11 11

the output is :

T

because, as far as I know, the line would be inside the rectangle ... or have I made mistake somewhere?

thank you

[the LA-Z-BOy]

to Almost Human:
As UFP2161 already figured out from the problem statement, the definition of intersection is

The line is said to intersect the rectangle if the line and the rectangle have at least one point in common.

In the sample you mentioned, all the points of the line is common with the rectangle. Hence it intersects and therefore output should be T.
Hope i'm clear.

[alu_mathics]

remember that in this problem
xtop<=xbottom
ytop>=ybottom
are not always true.
so you should consider this case.
Hope this will help you.

[Gazi Shaheen Hossain]

why this gives WA?
help me plz.
[cpp]#include <stdio.h>

void main()
{
long double xstart,ystart,xend,yend,xleft,ytop,xright,ybottom;
long double x,x1,x2,y,y1,y2,xmax,xmin,ymax,ymin;

while(scanf("%Lf %Lf %Lf %Lf %Lf %Lf %Lf %Lf",
&xstart,&ystart,&xend,&yend,&xleft,&ytop,&xright,&ybottom)==8)
{
x1=xstart;x2=xend;y1=ystart;y2=yend;
y=ytop;
x=(y-y1)*(x1-x2)/(y1-y2)+x1;
if(x>=xleft&&x<=xright)
{printf("T\n");continue;}

y=ybottom;
x=(y-y1)*(x1-x2)/(y1-y2)+x1;
if(x>=xleft&&x<=xright)
{printf("T\n");continue;}

x=xleft;
y=(x-x1)*(y1-y2)/(x1-x2)+y1;
if(y>=ybottom&&y<=ytop)
{printf("T\n");continue;}

x=xright;
y=(x-x1)*(y1-y2)/(x1-x2)+y1;
if(y>=ybottom&&y<=ytop)
{printf("T\n");continue;}
printf("F\n");
}
}[/cpp]

[Ndiyaa ndako]

What happens if y1=y2?

[shamim]

remember that in this problem
xtop<=xbottom
ytop>=ybottom
are not always true.
so you should consider this case.
Hope this will help you.

Yes, this is indeed true. I got plenty of wrong answers for this.
But what bothered me is, whenever a problem statement says left and top, they better use what they say, and not introduce contradictory critical inputs.

[shu]

The terms top left and bottom right do not imply any ordering of coordinates.

It means 'left' in this problem is not really-left in common sense
tricky statement it is.

[Anupam Pathak]

hi all,
i am trying to solve 191 Intersection in C++ but I am getting WA. I have considered as much cases as I could. My code is:-

#include<iostream>
using namespace std;

int check(float,float,float,float,float,float);


int main()
{
int N,i=0;
cin>>N;
float m,c,x,y;
int xstart,xend,ystart,yend,xleft,ytop,xright,ybottom,temp;
while(i!=N)
{
cin>>xstart>>ystart>>xend>>yend>>xleft>>ytop>>xright>>ybottom;
while(1)
{
if(((xstart<=xleft)&&(xstart>=xright))||((xstart>=xleft)&&(xstart<=xright)))
{
cout<<"T"<<endl;
break;
}
if(((xend<=xleft)&&(xend>=xright))||((xend>=xleft)&&(xend<=xright)))
{
cout<<"T"<<endl;
break;
}
if(xstart!=xend)
{
m=(float)(ystart-yend)/(float)(xstart-xend);
c=yend-(m*xend);
x=(ytop-c)/m;
if((x<=xright)&&(x>=xleft)&&check(xstart,ystart,xend,yend,x,ytop))
{
cout<<"T"<<endl;
break;
}
x=(ybottom-c)/m;
if((x<=xright)&&(x>=xleft)&&check(xstart,ystart,xend,yend,x,ybottom))
{
cout<<"T"<<endl;
break;
}
y=(m*xleft)+c;
if((y>=ybottom)&&(y<=ytop)&&check(xstart,ystart,xend,yend,xleft,y))
{
cout<<"T"<<endl;
break;
}
y=(m*xright)+c;
if((y>=ybottom)&&(y<=ytop)&&check(xstart,ystart,xend,yend,xright,y))
{
cout<<"T"<<endl;
break;
}
cout<<"F"<<endl;
break;
}
else
{
if((xstart>=xleft)&&(xstart<=xright)&&check(xstart,ystart,xend,yend,xstart,ytop))
{
cout<<"T"<<endl;
}
else
{
if((xstart>=xleft)&&(xstart<=xright)&&check(xstart,ystart,xend,yend,xstart,ybottom))
{
cout<<"T"<<endl;
}
else
cout<<"F"<<endl;
}
break;
}
}
i++;
}
return 0;
}


int check(float x1,float y1,float x2,float y2,float x,float y)
{
if(((x1<=x)&&(x2>=x))||((x1>=x)&&(x2<=x)))
{
if(((y1<=y)&&(y2>=y))||((y1>=y)&&(y2<=y)))
{
return 1;
}
}
return 0;
}

what's wrong with it........

Anupam Pathak

[898989]

Sorry i did not read your code
But her two notes...
In my code i remeember using epsilon for comparing floats
I remember there is a test case where line totaly inside rectangle
and this will be considered intersection
I hope this is useful