## 191 - Intersection

Moderator: Board moderators

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:
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
New poster
Posts: 2
Joined: Sat Jun 07, 2003 9:12 pm
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

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

### 191 WA , plizzzzzzzzzzzz help me

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

[/c]
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
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
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia
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
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia
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
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm
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
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Contact:
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.
Istiaque Ahmed [the LA-Z-BOy]

alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:
remember that in this problem
xtop<=xbottom
ytop>=ybottom
are not always true.
so you should consider this case.
cuii e

Gazi Shaheen Hossain
New poster
Posts: 7
Joined: Fri Sep 03, 2004 6:47 pm

### 191 WA

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
New poster
Posts: 21
Joined: Sat Sep 25, 2004 3:35 am
Location: Oaxaca de Ju
Contact:

### Slope

What happens if y1=y2?

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
alu_mathics wrote:remember that in this problem
xtop<=xbottom
ytop>=ybottom
are not always true.
so you should consider this case.
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
New poster
Posts: 6
Joined: Sat Jul 16, 2005 1:43 pm
Contact:
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.
best regards,
shu

Anupam Pathak
New poster
Posts: 7
Joined: Tue Jul 25, 2006 2:01 pm
Contact:

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
Trying to reduce complexity of the World.

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact: