191 - Intersection

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:

Post by paulhryu » Thu Jun 19, 2003 7:09 am

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

Post by Cool Guyz » Thu Jun 19, 2003 8:36 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

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

191 WA , plizzzzzzzzzzzz help me

Post by Riyad » Thu Aug 14, 2003 10:41 pm



[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]
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Sat Aug 16, 2003 12:34 am

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

Post by Joseph Kurniawan » Sun Aug 17, 2003 5:59 am

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. :wink:

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by Joseph Kurniawan » Sun Aug 17, 2003 6:11 am

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

Post by Almost Human » Tue Mar 09, 2004 8:13 am

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

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Tue Mar 09, 2004 11:25 am

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]

User avatar
alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:

Post by alu_mathics » Tue Mar 09, 2004 2:22 pm

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

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

191 WA

Post by Gazi Shaheen Hossain » Mon Sep 13, 2004 1:10 pm

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]

User avatar
Ndiyaa ndako
New poster
Posts: 21
Joined: Sat Sep 25, 2004 3:35 am
Location: Oaxaca de Ju
Contact:

Slope

Post by Ndiyaa ndako » Tue Sep 28, 2004 8:45 pm

What happens if y1=y2?

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sat Jul 09, 2005 3:38 pm

alu_mathics wrote: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 :evil: is, whenever a problem statement says left and top, they better use what they say, and not introduce contradictory critical inputs. :evil:

shu
New poster
Posts: 6
Joined: Sat Jul 16, 2005 1:43 pm
Contact:

Post by shu » Sun Aug 14, 2005 7:54 am

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:

191 Wrong Answer

Post by Anupam Pathak » Tue Jul 25, 2006 2:05 pm

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:

Post by 898989 » Thu Jul 27, 2006 6:17 pm

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
Sleep enough after death, it is the time to work.
Mostafa Saad

Post Reply

Return to “Volume 1 (100-199)”