## 191 - Intersection

Moderator: Board moderators

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:
Please read more carefully on the input description of the problem. You have some assumption~

tam
New poster
Posts: 3
Joined: Tue Jul 02, 2002 7:05 am
The Question Said "The terms and do not imply any ordering of coordinates. " .
I don't know what is it about ...........
( I don't understand .... what is the error for the input........)
Sorry.

If I paste the code,

[pascal]

if (rx1 > rx2) then begin t:=rx1; rx1:=rx2; rx2:=t; end;
if (ry2 > ry1) then begin t:=ry1; ry1:=ry2; ry2:=t; end;

[/pascal]

Mart
New poster
Posts: 18
Joined: Wed Jun 12, 2002 1:00 pm
Firstly, you need that extra code.
Secondly, strange to go with x1<=x2 but y1>=y2, it's bound to cause confusion in your maths, but whatever.
Thirdly, try:

1
4 9 4 7 1 5 7 1

correct output:
F

taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:

### 191 - Intersection

Can any one of u explainn what does this means:
The terms top left and bottom right do not imply any ordering of coordinates.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
The input can contain coordinates with left>right and/or bottom>top. You have to swap the values, so that left<right and bottom<top.
Example:
4 9 11 2 7 1 1 5
process with:
4 9 11 2 1 5 7 1

taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:
But it is certain( i suppose) that the 5th and 7th elements in a line of input are the x coordinates of top left & bottom right( not necessarily in order)
and similarly 6th and 8th element are y coordinates.

Am i correct

Mart
New poster
Posts: 18
Joined: Wed Jun 12, 2002 1:00 pm
You are correct.

taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:
Judge is giving wrong answer for my prog but i m unable to find a single case where my prog is giving wrong answer.
Can u help me out?

Code: Select all

``````#include<stdio.h>

void func(int xstart,int ystart,int xend,int yend,int x1,int y1,int x2,int y3);
int point_in_linesegment(float x,float y,int xstart,int  ystart,int  xend,int  yend);
float value_y_given_x(int x,int xstart,int ystart,int xend,int yend);
float value_x_given_y(int y,int xstart,int ystart,int xend,int yend);

main()
{int xstart,ystart,xend,yend,topleft1,topleft2,bottomright1,bottomright2,n,x1,y1,x2,y3,i;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&xstart);
scanf("%d",&ystart);
scanf("%d",&xend);
scanf("%d",&yend);
scanf("%d",&topleft1);
scanf("%d",&topleft2);
scanf("%d",&bottomright1);
scanf("%d",&bottomright2);

if( topleft1 < bottomright1)
{ x1 = topleft1;
y1 = topleft2;
x2 = bottomright1;
y3 = bottomright2;
}
else
{ x1 = bottomright1;
y1 = bottomright2;
x2 = topleft1;
y3 = topleft2;
}

func(xstart,ystart,xend,yend,x1,y1,x2,y3);
}
}

void func(int xstart,int ystart,int xend,int yend,int x1,int y1,int x2,int y3)
{ float x,y;
if(ystart == yend)/* IF #1  */
{/* Checking if any of end pt of the line segment is any of the horizontal lines of rect */
if( (ystart == y1)||(ystart == y3) )
if( ((xstart >= x1)&&(xstart <= x2))|| ((xend >= x1)&&(xend <= x2))|| ((xstart <=x1)&&(xend >=x2))|| ((xstart >= x2)&&(xend <=x1))   )
{ printf("T\n");
return;
}
else
{ printf("F\n");
return;
}

if( (ystart > y1)||(ystart < y3) )
{ printf("F\n");
return;
}
if( (ystart < y1)&&(ystart > y3) )
{
if(   ( (xstart<x1)&&(xend<x1) )|| ( (xstart>x2)&&(xend>x2) )  || ((xstart>x1)&&(xend<x2)) ||( (xstart<x2)&&(xend>x1)) )
{ printf("F\n");
return;
}
else
{ printf("T\n");
return;
}
}
}/*END of IF #1  */
/* checked when line segment is horizontal  */

if(xstart == xend)/* IF #2  */
{/* Checking if any of end pt of the line segment is on any of the vertical lines of rect */
if( (xstart == x1)||(xstart == x2) )
if( ((ystart >= y3)&&(ystart <= y1))|| ((yend >= y3)&&(yend <= y1))|| (( ystart <= y3)&&(yend >= y1))|| (( ystart >= y1)&&(yend <= y3))   )
{ printf("T\n");
return;
}
else
{ printf("F\n");
return;
}

if( (xstart < x1)||(xstart > x2) )
{ printf("F\n");
return;
}
if( (ystart < y1)&&(ystart > y3) )
{
if(   ( (ystart<y3)&&(yend<y3) )|| ( (ystart>y1)&&(yend>y1) )  || ((ystart>y3)&&(yend<y1)) || ((ystart<y1)&&(yend>y3)) )
{ printf("F\n");
return;
}
else
{ printf("T\n");
return;
}
}
}/*END of IF #2  */
/* checked when line segment is vertical  */

/* after checking that line segment is not parallel to any side of retangle */
/* checking the top line of rectangle */
x = value_x_given_y(y1,xstart, ystart, xend, yend);/* this gives the value of x if line intersects top line of rectangle*/
/* printf("\n At 7  x= %f y = %d\n",x,y1); */
if( x>=x1 && x<=x2 && (point_in_linesegment(x,y1,xstart, ystart, xend, yend) == 1)   )
{ printf("T\n");
return;
}

/* checking the bottom line of rectangle */
x = value_x_given_y(y3,xstart, ystart, xend, yend);
if( x>=x1 && x<=x2 && (point_in_linesegment(x,y3,xstart, ystart, xend, yend) == 1)   )
{ printf("T\n");
return;
}

/* checking the left line of rectangle */
y = value_y_given_x(x1,xstart, ystart, xend, yend);
if( y>=y3 && y<=y1 && (point_in_linesegment(x1,y,xstart, ystart, xend, yend) == 1)   )
{ printf("T\n");
return;
}

/* checking the right line of rectangle */
y = value_y_given_x(x2,xstart, ystart, xend, yend);
if( y>=y3 && y<=y1 && (point_in_linesegment(x2,y,xstart, ystart, xend, yend) == 1)   )
{ printf("T\n");
return;
}

/* When non of the cases appeared  */
printf("F\n");
return;

}

int point_in_linesegment(float x,float y,int xstart,int  ystart,int  xend,int  yend)
{float a,b,len_sqr;

if(   (( x== xend)&&(y = yend) )||( (x == xstart)&&(y == ystart) )   )
return(1);/* 1 means the point is on the line segment  */

len_sqr = (xstart - xend)*(xstart - xend) + (ystart - yend)*(ystart - yend);
a = (x - xend)*(x - xend) + (y - yend)*(y - yend);
b = (xstart - x)*(xstart - x) + (ystart - y)*(ystart - y);

/* a = (y - yend)/(x - xend);
b = (y - ystart)/(x - xstart);  */

/* if( ( a>0 && b>0)||(a<0 && b<0) ) */
if( a <= len_sqr && b <= len_sqr)
return(1);
else
return(0);
}

float value_y_given_x(int x,int xstart,int ystart,int xend,int yend)
{float a;
a= ystart + (x - xstart)*(yend - ystart)/(xend - xstart);
return(a);
}

float value_x_given_y(int y,int xstart,int ystart,int xend,int yend)
{float b;
b = xstart + (y - ystart)*(xend - xstart)/(yend - ystart);
return(b);
}

``````

Mart
New poster
Posts: 18
Joined: Wed Jun 12, 2002 1:00 pm
if( topleft1 < bottomright1)
{ x1 = topleft1;
y1 = topleft2;
x2 = bottomright1;
y3 = bottomright2;
}
else
{ x1 = bottomright1;
y1 = bottomright2;
x2 = topleft1;
y3 = topleft2;
}

It's not enough to compare just the X values. You need to compare the X and Y values independently and swap either (or both or neither, depending on the values).
i.e. you need both x1<=x2 and y3<=y1 (x1,y1,x2 and y3?? weird).

Mart

taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:
I have changed it to

Code: Select all

``````if( (topleft1 < bottomright1)&&( topleft2 > bottomright2)   )
{ x1 = topleft1;
y1 = topleft2;
x2 = bottomright1;
y3 = bottomright2;
}
if( (topleft1 < bottomright1)&&( topleft2 < bottomright2)   )
{ x1 = topleft1;
y3 = topleft2;
x2 = bottomright1;
y1 = bottomright2;
}
if( (topleft1 > bottomright1)&&( topleft2 > bottomright2)  )
{ x1 = bottomright1;
y3 = bottomright2;
x2 = topleft1;
y1 = topleft2;
}
if( (topleft1 > bottomright1)&&( topleft2 > bottomright2)  )
{  x2 = topleft1;
y3 = topleft2;
x1 = bottomright1;
y1 = bottomright2;
}

``````

my rectangle is

x1 y1........................ x2 y1

x1 y3 ......................... x2 y3

I understand y3 is weird.I am sorry for taking that choice.

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

### 191 WA

I can't understand why my program gets WA:

[pascal]Program p191;

Const Eps = 1e-7;

Type TPoint = Record X,Y : Extended; End;
TLine = Record A,B,C : Extended; End;

Var p1,p2,e1,e2 : TPoint;
tmp : Extended;
N,t : Integer;
l : TLine;

Procedure MakeLine(T1,T2:TPoint;Var L:TLine);
begin
l.a:=t1.y-t2.y;
l.b:=t2.x-t1.x;
l.c:=-t1.x*(t1.y-t2.y)+t1.y*(t1.x-t2.x);
end;

Function Min(a,b : extended) : extended;
begin
if a<b then Min:=a else Min:=b;
end;

Function Max(a,b : extended) : extended;
begin
if a>b then Max:=a else Max:=b;
end;

Function Check : boolean;
var y1,y2,x1,x2 : extended;
begin
if (p2.x-e1.x>-eps)and(e1.x-p1.x<eps) then
if (p1.y-e1.y>-eps)and(e1.y-p2.y<eps) then begin
Check:=True;
exit;
end;
if (p2.x-e2.x>-eps)and(e2.x-p1.x<eps) then
if (p1.y-e2.y>-eps)and(e2.y-p2.y<eps) then begin
Check:=True;
exit;
end;
if abs(e1.x-e2.x)<eps then begin
Check:=True;
if (e1.x-p1.x>-eps)and(p2.x-e1.x>-eps)and
(min(e1.y,e2.y)-eps<p1.y)and(max(e1.y,e2.y)+eps>p2.y) then exit;
Check:=False;
exit;
end else
if abs(e1.y-e2.y)<eps then begin
Check:=True;
if (e1.y-p2.y>-eps)and(p1.y-e1.y>-eps)and
(min(e1.x,e2.x)-eps<p2.x)and(max(e1.y,e2.y)+eps>p1.x) then exit;
Check:=False;
exit;
end;
y1:=-(l.a*p1.x+l.c)/l.b;
if (p1.y-y1>-eps)and(y1-p2.y>-eps) then begin Check:=True; exit; end;
y2:=-(l.a*p2.x+l.c)/l.b;
if (p1.y-y2>-eps)and(y2-p2.y>-eps) then begin Check:=True; exit; end;
x1:=-(l.b*p1.y+l.c)/l.b;
if (p2.x-x1>-eps)and(x1-p1.x>-eps) then begin Check:=True; exit; end;
x2:=-(l.b*p1.y+l.c)/l.b;
if (p2.x-x2>-eps)and(x2-p1.x>-eps) then begin Check:=True; exit; end;
Check:=False;
end;

begin
for t:=1 to N do begin
MakeLine(e1,e2,l);
if p1.x>p2.x then begin
tmp:=p1.x;
p1.x:=p2.x;
p2.x:=tmp;
end;
if p1.y<p2.y then begin
tmp:=p1.y;
p1.y:=p2.y;
p2.y:=tmp;
end;
if Check then Writeln('T') else Writeln('F');
end;
end.[/pascal]

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia
I found some mistakes, but still WA

[pascal]Program p191;

Const Eps = 1e-7;

Type TPoint = Record X,Y : Extended; End;
TLine = Record A,B,C : Extended; End;

Var p1,p2,e1,e2 : TPoint;
tmp : Extended;
N,t : Integer;
l : TLine;

Procedure MakeLine(T1,T2:TPoint;Var L:TLine);
begin
l.a:=t1.y-t2.y;
l.b:=t2.x-t1.x;
l.c:=-t1.x*(t1.y-t2.y)+t1.y*(t1.x-t2.x);
end;

Function Min(a,b : extended) : extended;
begin
if a<b then Min:=a else Min:=b;
end;

Function Max(a,b : extended) : extended;
begin
if a>b then Max:=a else Max:=b;
end;

Function Check : boolean;
var y1,y2,x1,x2 : extended;
begin
if (p2.x-e1.x>-eps)and(e1.x-p1.x<eps) then
if (p1.y-e1.y>-eps)and(e1.y-p2.y<eps) then begin
Check:=True;
exit;
end;
if (p2.x-e2.x>-eps)and(e2.x-p1.x<eps) then
if (p1.y-e2.y>-eps)and(e2.y-p2.y<eps) then begin
Check:=True;
exit;
end;
if abs(e1.x-e2.x)<eps then begin
Check:=True;
if (e1.x-p1.x>-eps)and(p2.x-e1.x>-eps)and
(min(e1.y,e2.y)-eps<p1.y)and(max(e1.y,e2.y)+eps>p2.y) then exit;
Check:=False;
exit;
end else
if abs(e1.y-e2.y)<eps then begin
Check:=True;
if (e1.y-p2.y>-eps)and(p1.y-e1.y>-eps)and
(min(e1.x,e2.x)-eps<p2.x)and(max(e1.y,e2.y)+eps>p1.x) then exit;
Check:=False;
exit;
end;
y1:=-(l.a*p1.x+l.c)/l.b;
if (p1.y-y1>-eps)and(y1-p2.y>-eps)and
(min(e1.y,e2.y)-eps<y1)and(max(e1.y,e2.y)+eps>y1) then begin Check:=True; exit; end;
y2:=-(l.a*p2.x+l.c)/l.b;
if (p1.y-y2>-eps)and(y2-p2.y>-eps)and
(min(e1.y,e2.y)-eps<y2)and(max(e1.y,e2.y)+eps>y2) then begin Check:=True; exit; end;
x1:=-(l.b*p1.y+l.c)/l.b;
if (p2.x-x1>-eps)and(x1-p1.x>-eps)and
(min(e1.x,e2.x)-eps<x1)and(max(e1.x,e2.x)+eps>x1) then begin Check:=True; exit; end;
x2:=-(l.b*p1.y+l.c)/l.b;
if (p2.x-x2>-eps)and(x2-p1.x>-eps)and
(min(e1.x,e2.x)-eps<x2)and(max(e1.x,e2.x)+eps>x2) then begin Check:=True; exit; end;
Check:=False;
end;

begin
for t:=1 to N do begin
MakeLine(e1,e2,l);
if p1.x>p2.x then begin
tmp:=p1.x;
p1.x:=p2.x;
p2.x:=tmp;
end;
if p1.y<p2.y then begin
tmp:=p1.y;
p1.y:=p2.y;
p2.y:=tmp;
end;
if Check then Writeln('T') else Writeln('F');
end;
end.[/pascal]

Mart
New poster
Posts: 18
Joined: Wed Jun 12, 2002 1:00 pm
You still fail the case:
4 9 4 7 1 5 7 1
which should return F

It can fail for topleft1==bottomright1 or topleft2==bottomright2

You have some ambigious IF IF ELSE statements.

> if( (( x== xend)&&(y = yend) )||( (x == xstart)&&(y == ystart) ) )
Should be y==yend.

Vertical (or horizontal) lines can get through their entire IF cases and carry on to code that assumes the line is diagonal (and gives division by zero if the line isn't diagonal). You need to trap more cases (or maybe it is always "F") at the end of the vertical and horizontal sections.

> I understand y3 is weird.I am sorry for taking that choice.

Don't be sorry - I was just being cheeky

Mart

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia
I get Accepted at last!

taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:
again WA...had i left any case this time also? ...Plz help

Code: Select all

``````
#include<stdio.h>

void func(int xstart,int ystart,int xend,int yend,int x1,int y1,int x2,int y3);
int point_in_linesegment(float x,float y,int xstart,int  ystart,int  xend,int  yend);
float value_y_given_x(int x,int xstart,int ystart,int xend,int yend);
float value_x_given_y(int y,int xstart,int ystart,int xend,int yend);

main()
{int xstart,ystart,xend,yend,topleft1,topleft2,bottomright1,bottomright2,n,x1,y1,x2,y3,i;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&xstart);
scanf("%d",&ystart);
scanf("%d",&xend);
scanf("%d",&yend);
scanf("%d",&topleft1);
scanf("%d",&topleft2);
scanf("%d",&bottomright1);
scanf("%d",&bottomright2);

if( (topleft1 < bottomright1)&&( topleft2 > bottomright2)   )
{ x1 = topleft1;
y1 = topleft2;
x2 = bottomright1;
y3 = bottomright2;
}
if( (topleft1 < bottomright1)&&( topleft2 < bottomright2)   )
{ x1 = topleft1;
y3 = topleft2;
x2 = bottomright1;
y1 = bottomright2;
}
if( (topleft1 > bottomright1)&&( topleft2 > bottomright2)  )
{ x1 = bottomright1;
y3 = bottomright2;
x2 = topleft1;
y1 = topleft2;
}
if( (topleft1 > bottomright1)&&( topleft2 < bottomright2)  )
{  x2 = topleft1;
y3 = topleft2;
x1 = bottomright1;
y1 = bottomright2;
}

/* printf(" %d %d %d %d %d %d %d %d",xstart,ystart,xend,yend,x1,y1,x2,y3);exit(1); */
func(xstart,ystart,xend,yend,x1,y1,x2,y3);
}
}

void func(int xstart,int ystart,int xend,int yend,int x1,int y1,int x2,int y3)
{ float x,y;
if(ystart == yend)/* IF #1  *//* line segment is horizontal */
{/* Checking if any of end pt of the line segment is any of the horizontal lines of rect */
if( (ystart == y1)||(ystart == y3) )
if( ((xstart >= x1)&&(xstart <= x2))|| ((xend >= x1)&&(xend <= x2))|| ((xstart <=x1)&&(xend >=x2))|| ((xstart >= x2)&&(xend <=x1))   )
{ printf("T\n");
return;
}
else
{ printf("F\n");
return;
}

if( (ystart > y1)||(ystart < y3) )
{ printf("F\n");
return;
}/* Line is either above or below the rectangle */

if( xstart > x2 && xend > x2)
{ printf("F\n");
return;
}/*  line segm is entirely right of  rectangle  */

if( xstart < x1 && xend < x1)
{ printf("F\n");
return;
}/*  line segm is entirely left of rectangle  */

if( xstart < x2 && xend < x2 && xstart > x1 && xend > x1 )
{ printf("F\n");
return;
}/* horizontal line segm is entirely inside rectangle  */

printf("T\n");
return;

}/*END of IF #1  */
/* checked when line segment is horizontal  */

if(xstart == xend)/* IF #2  *//* the line segm is vertical */
{/* Checking if any of end pt of the line segment is on any of the vertical lines of rect */
if( (xstart == x1)||(xstart == x2) )
if( ((ystart >= y3)&&(ystart <= y1))|| ((yend >= y3)&&(yend <= y1))|| (( ystart <= y3)&&(yend >= y1))|| (( ystart >= y1)&&(yend <= y3))   )
{ printf("T\n");
return;
}
else
{ printf("F\n");
return;
}

if( (xstart < x1)||(xstart > x2) )
{ printf("F\n");
return;
}

if( ystart > y1 && yend > y1)
{ printf("F\n");
return;
}/* vertical line segm is entirely above rectangle  */

if( ystart < y3 && yend < y3)
{ printf("F\n");
return;
}/* vertical line segm is entirely below rectangle  */

if( ystart < y1 && yend < y1 && ystart > y3 && yend > y3 )
{ printf("F\n");
return;
}/* vertical line segm is entirely inside rectangle  */

printf("T\n");
return;
}/*END of IF #2  */
/* checked when line segment is vertical  */

/* after checking that line segment is not parallel to any side of retangle */
/* checking the top line of rectangle */
x = value_x_given_y(y1,xstart, ystart, xend, yend);/* this gives the value of x if line intersects top line of rectangle*/
/* printf("\n At 7  x= %f y = %d\n",x,y1); */
if( x>=x1 && x<=x2 && (point_in_linesegment(x,y1,xstart, ystart, xend, yend) == 1)   )
{ printf("T\n");
return;
}

/* checking the bottom line of rectangle */
x = value_x_given_y(y3,xstart, ystart, xend, yend);
if( x>=x1 && x<=x2 && (point_in_linesegment(x,y3,xstart, ystart, xend, yend) == 1)   )
{ printf("T\n");
return;
}

/* checking the left line of rectangle */
y = value_y_given_x(x1,xstart, ystart, xend, yend);
if( y>=y3 && y<=y1 && (point_in_linesegment(x1,y,xstart, ystart, xend, yend) == 1)   )
{ printf("T\n");
return;
}

/* checking the right line of rectangle */
y = value_y_given_x(x2,xstart, ystart, xend, yend);
if( y>=y3 && y<=y1 && (point_in_linesegment(x2,y,xstart, ystart, xend, yend) == 1)   )
{ printf("T\n");
return;
}

/* When non of the cases appeared  */
printf("F\n");
return;

}

int point_in_linesegment(float x,float y,int xstart,int  ystart,int  xend,int  yend)
{float a,b,len_sqr;

if(   (( x== xend)&&(y == yend) )||( (x == xstart)&&(y == ystart) )   )
return(1);/* 1 means the point is on the line segment  */

len_sqr = (xstart - xend)*(xstart - xend) + (ystart - yend)*(ystart - yend);
a = (x - xend)*(x - xend) + (y - yend)*(y - yend);
b = (xstart - x)*(xstart - x) + (ystart - y)*(ystart - y);

/* a = (y - yend)/(x - xend);
b = (y - ystart)/(x - xstart);  */

/* if( ( a>0 && b>0)||(a<0 && b<0) ) */
if( a <= len_sqr && b <= len_sqr)
return(1);
else
return(0);
}

float value_y_given_x(int x,int xstart,int ystart,int xend,int yend)
{float a;
a= ystart + (x - xstart)*(yend - ystart)/(xend - xstart);
return(a);
}

float value_x_given_y(int y,int xstart,int ystart,int xend,int yend)
{float b;
b = xstart + (y - ystart)*(xend - xstart)/(yend - ystart);
return(b);
}

``````