Posted: Mon Jul 08, 2002 2:17 pm
How about:
4 9 11 2 12 5 1 5
4 9 11 2 4 9 4 9
result:
T
T
4 9 11 2 12 5 1 5
4 9 11 2 4 9 4 9
result:
T
T
The 1st one is a line
& 2nd one is a point
These are not rectangle.
Page 3 of 7
Posted: Mon Jul 08, 2002 3:28 pm
Posted: Mon Jul 08, 2002 4:07 pm
Oh, they are~
To me, a line is a "contracted" rectangle, and a point is a "contracted" line~
This implies that you have not considered some special cases of the problem
To me, a line is a "contracted" rectangle, and a point is a "contracted" line~
This implies that you have not considered some special cases of the problem
Posted: Mon Jul 08, 2002 5:59 pm
i cosidered special cases but got WA
Plz help
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;
float x,y;
int z;
scanf("%d",&n);
for(i=0;i<n;i++)
{ z =0;
scanf("%d",&xstart);
scanf("%d",&ystart);
scanf("%d",&xend);
scanf("%d",¥d);
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;
}
if( (topleft1 == bottomright1) && (topleft2 != bottomright2) )
{/* when rect is actually a vertical line */
x = topleft1;
y = value_y_given_x(x,xstart, ystart, xend, yend);
if( point_in_linesegment(x,y,xstart,ystart,xend,yend) == 1)
printf("T\n");
else
printf("F\n");
z =1;/* special case has applied */
}
if( (topleft1 != bottomright1) && (topleft2 == bottomright2) )
{/* when rect is actually a horizontal line */
y = topleft2;
x = value_x_given_y(y,xstart, ystart, xend, yend);
if( point_in_linesegment(x,y,xstart,ystart,xend,yend) == 1)
printf("T\n");
else
printf("F\n");
z =1;
}
if( (topleft1 == bottomright1) && (topleft2 == bottomright2) )
{/* when rect is actually a point */
x = topleft1;
y = topleft2;
if( point_in_linesegment(x,y,xstart,ystart,xend,yend) == 1)
printf("T\n");
else
printf("F\n");
z =1;
}
/* printf(" %d %d %d %d %d %d %d %d",xstart,ystart,xend,yend,x1,y1,x2,y3);exit(1); */
if(z != 1)/* special cases didn't worked */
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);
}
Posted: Mon Jul 08, 2002 11:47 pm
Ok, how about:
1 1 10 10 6 5 8 5
F
You have code to cover this case (and similar ones) but it is wrong.
1 1 10 10 6 5 8 5
F
You have code to cover this case (and similar ones) but it is wrong.
Posted: Tue Jul 09, 2002 7:25 am
Again WA.....i have changed quite a lot...
Code: Select all
#include<stdio.h>
#include<math.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;
float x,y;
int z;
scanf("%d",&n);
for(i=0;i<n;i++)
{ z =0;
scanf("%d",&xstart);
scanf("%d",&ystart);
scanf("%d",&xend);
scanf("%d",¥d);
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;
}
if( (topleft1 == bottomright1) && (topleft2 != bottomright2) )
{/* when rect is actually a vertical line */
x = topleft1;
y = value_y_given_x(x,xstart, ystart, xend, yend);
if( ( y<= topleft2 && y>= bottomright2 )||( y>= topleft2 && y<= bottomright2 ) )
printf("T\n");
else
printf("F\n");
z =1;/* special case has applied */
}
if( (topleft1 != bottomright1) && (topleft2 == bottomright2) )
{/* when rect is actually a horizontal line */
y = topleft2;
x = value_x_given_y(y,xstart, ystart, xend, yend);
/* printf("x = %f y = %f ",x,y); */
if( ( x<= topleft1 && x>= bottomright1 )||( x>= topleft1 && x<= bottomright1 ) )
printf("T\n");
else
printf("F\n");
z =1;
}
if( (topleft1 == bottomright1) && (topleft2 == bottomright2) )
{/* when rect is actually a point */
x = topleft1;
y = topleft2;
if( point_in_linesegment(x,y,xstart,ystart,xend,yend) == 1)
printf("T\n");
else
printf("F\n");
z =1;
}
/* printf(" %d %d %d %d %d %d %d %d",xstart,ystart,xend,yend,x1,y1,x2,y3);exit(1); */
if(z != 1)/* special cases didn't worked */
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,a1,b1,len;
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);
len = sqrt(len_sqr);
a1 = sqrt(a);
b1 = sqrt(b);
/* a = (y - yend)/(x - xend);
b = (y - ystart)/(x - xstart); */
/* if( ( a>0 && b>0)||(a<0 && b<0) ) */
if( a1+b1 == len)
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);
}
Posted: Tue Jul 09, 2002 2:01 pm
Ok the obvious similar special case to the previous ones:
5 5 5 5 4 4 6 6
T
Now I couldn't quite see where you were missing this at first, because you appear to cover all the relevant cases, but then I realised that you've misunderstood the problem. Go back and read the description again, in particular the definition of a rectangle.
Mart.
5 5 5 5 4 4 6 6
T
Now I couldn't quite see where you were missing this at first, because you appear to cover all the relevant cases, but then I realised that you've misunderstood the problem. Go back and read the description again, in particular the definition of a rectangle.
Mart.
Posted: Tue Jul 09, 2002 6:51 pm
this time i understnd what the problem meant by rectangle...i changed a lot...but again WA
Code: Select all
#include<stdio.h>
#include<math.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;
float x,y;
int z;
scanf("%d",&n);
for(i=0;i<n;i++)
{ z =0;
scanf("%d",&xstart);
scanf("%d",&ystart);
scanf("%d",&xend);
scanf("%d",¥d);
scanf("%d",&topleft1);
scanf("%d",&topleft2);
scanf("%d",&bottomright1);
scanf("%d",&bottomright2);
if( (xstart == xend)&&(ystart == yend) )/* the line is itself a point */
{/* printf("line is a pt \n"); */
if( (topleft1 == bottomright1)&&(topleft2 == bottomright2) )/* rect is also a point */
{ if((xstart == topleft1)&&(ystart == topleft2) )
printf("T\n");
else
printf("F\n");
continue;
}
/* when rectangle is not a point */
if( ( ( (xstart <= topleft1)&&(xstart >= bottomright1) )||
( (xstart >= topleft1)&&(xstart <= bottomright1) ) )&&
( ( (ystart <= topleft2)&&(ystart >= bottomright2) )||
( (ystart >= topleft2)&&(ystart <= bottomright2) ) ) )
/* the point is checked to be in or on the rectangle */
{ printf("T\n");
continue;
}
printf("F\n");
continue;
}/* END of if */
/* verified the case when the line is actually a point */
if( (topleft1 == bottomright1)&&(topleft2 == bottomright2) )
{/* rectangle is a point but the line is not a point */
if( point_in_linesegment(topleft1,topleft2,xstart, ystart, xend,yend) == 1)
printf("T\n");
else
printf("F\n");
continue;
}
/* special cases when either or both line or rect are point has been verified */
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;
}
if( (topleft1 == bottomright1) && (topleft2 != bottomright2) )
{/* when rect is actually a vertical line */
if( xstart == xend)/* line segm is also vertical */
{ if(xstart != topleft1)
{printf("F\n");
continue;
}
if( point_in_linesegment(xstart,ystart,topleft1,topleft2,bottomright1,bottomright2) == 1 )
{printf("T\n");
continue;
}
if( point_in_linesegment(xend,yend,topleft1,topleft2,bottomright1,bottomright2) == 1 )
{printf("T\n");
continue;
}
if( point_in_linesegment(topleft1,topleft2,xstart,ystart,xend,yend) == 1 )
{printf("T\n");
continue;
}
if( point_in_linesegment(bottomright1,bottomright2,xstart,ystart,xend,yend) == 1 )
{printf("T\n");
continue;
}
}/* checked case when line segm is also vertical */
x = topleft1;
y = value_y_given_x(x,xstart, ystart, xend, yend);
if( ( y<= topleft2 && y>= bottomright2 )||( y>= topleft2 && y<= bottomright2 ) )
printf("T\n");
else
printf("F\n");
continue;
}
if( (topleft1 != bottomright1) && (topleft2 == bottomright2) )
{/* when rect is actually a horizontal line */
if( ystart == yend)/* line segm is also horiz */
{ if(ystart != topleft2)
{printf("F\n");
continue;
}
if( point_in_linesegment(xstart,ystart,topleft1,topleft2,bottomright1,bottomright2) == 1 )
{printf("T\n");
continue;
}
if( point_in_linesegment(xend,yend,topleft1,topleft2,bottomright1,bottomright2) == 1 )
{printf("T\n");
continue;
}
if( point_in_linesegment(topleft1,topleft2,xstart,ystart,xend,yend) == 1 )
{printf("T\n");
continue;
}
if( point_in_linesegment(bottomright1,bottomright2,xstart,ystart,xend,yend) == 1 )
{printf("T\n");
continue;
}
}/* checked case when line segm is also vertical */
y = topleft2;
x = value_x_given_y(y,xstart, ystart, xend, yend);
/* printf("x = %f y = %f ",x,y); */
if( ( x<= topleft1 && x>= bottomright1 )||( x>= topleft1 && x<= bottomright1 ) )
printf("T\n");
else
printf("F\n");
continue;
}
/* printf(" %d %d %d %d %d %d %d %d",xstart,ystart,xend,yend,x1,y1,x2,y3);exit(1); */
/* now if the line and rectangle are as per convention the prog has reached here */
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 */
{
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 */
printf("T\n");
return;
}/*END of IF #1 */
/* checked when line segment is horizontal */
if(xstart == xend)/* IF #2 *//* the line segm is vertical */
{
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 */
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 if any of the end pt of line segment is inside rectangle */
if( (xstart >= x1)&&(xstart <= x2)&&(ystart >= y3)&&(ystart <= y1) )
printf("T\n");
if( (xend >= x1)&&(xend <= x2)&&(yend >= y3)&&(yend <= y1) )
printf("T\n");
/* 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,a1,b1,len;
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);
len = sqrt(len_sqr);
a1 = sqrt(a);
b1 = sqrt(b);
/* a = (y - yend)/(x - xend);
b = (y - ystart)/(x - xstart); */
/* if( ( a>0 && b>0)||(a<0 && b<0) ) */
if( a1+b1 == len)
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);
}
Posted: Wed Jul 10, 2002 2:21 am
Hmm - there are a few obvious errors in your code.
e.g. Some printf statements without a return or continue after them
you use:
if (a1+b1 == len)
with floats - not a good idea. You might want to consider how floating point accuracy (or lack of it) might be affecting you. (Actually my code was accepted without accuracy checks, although it misses some cases I constructed later... (gets them now though)).
Also you have some potential division by zero problems in your line segment and rectangle are horizontal (or vertical) checks (although if you get WA rather than runtime error you can assume those cases never happen...)
You're probably getting pretty frustrated with this problem (I certainly would be) but I think your program has got very bloated, and you might consider starting from scratch. You really don't need any more than a point-in-rectangle test and then about 4 or 5 lines for each (axis-aligned) side of the rectangle.
Mart.
e.g. Some printf statements without a return or continue after them
you use:
if (a1+b1 == len)
with floats - not a good idea. You might want to consider how floating point accuracy (or lack of it) might be affecting you. (Actually my code was accepted without accuracy checks, although it misses some cases I constructed later... (gets them now though)).
Also you have some potential division by zero problems in your line segment and rectangle are horizontal (or vertical) checks (although if you get WA rather than runtime error you can assume those cases never happen...)
You're probably getting pretty frustrated with this problem (I certainly would be) but I think your program has got very bloated, and you might consider starting from scratch. You really don't need any more than a point-in-rectangle test and then about 4 or 5 lines for each (axis-aligned) side of the rectangle.
Mart.
Posted: Wed Jul 10, 2002 7:55 am
i have changed as per your advice ..but still getting WA....i can't figure out why???
Code: Select all
#include<stdio.h>
#include<stdlib.h>
#include<math.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;
float x,y;
int z;
scanf("%d",&n);
for(i=0;i<n;i++)
{ z =0;
scanf("%d",&xstart);
scanf("%d",&ystart);
scanf("%d",&xend);
scanf("%d",¥d);
scanf("%d",&topleft1);
scanf("%d",&topleft2);
scanf("%d",&bottomright1);
scanf("%d",&bottomright2);
if( (xstart == xend)&&(ystart == yend) )/* the line is itself a point */
{/* printf("line is a pt \n"); */
if( (topleft1 == bottomright1)&&(topleft2 == bottomright2) )/* rect is also a point */
{ if((xstart == topleft1)&&(ystart == topleft2) )
printf("T\n");
else
printf("F\n");
continue;
}
/* when rectangle is not a point */
if( ( ( (xstart <= topleft1)&&(xstart >= bottomright1) )||
( (xstart >= topleft1)&&(xstart <= bottomright1) ) )&&
( ( (ystart <= topleft2)&&(ystart >= bottomright2) )||
( (ystart >= topleft2)&&(ystart <= bottomright2) ) ) )
/* the point is checked to be in or on the rectangle */
{ printf("T\n");
continue;
}
printf("F\n");
continue;
}/* END of if */
/* verified the case when the line is actually a point */
if( (topleft1 == bottomright1)&&(topleft2 == bottomright2) )
{/* rectangle is a point but the line is not a point */
if( point_in_linesegment(topleft1,topleft2,xstart, ystart, xend,yend) == 1)
printf("T\n");
else
printf("F\n");
continue;
}
/* special cases when either or both line or rect are point has been verified */
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;
}
if( (topleft1 == bottomright1) && (topleft2 != bottomright2) )
{/* when rect is actually a vertical line */
if( xstart == xend)/* line segm is also vertical */
{ if(xstart != topleft1)
{printf("F\n");
continue;
}
if( point_in_linesegment(xstart,ystart,topleft1,topleft2,bottomright1,bottomright2) == 1 )
{printf("T\n");
continue;
}
if( point_in_linesegment(xend,yend,topleft1,topleft2,bottomright1,bottomright2) == 1 )
{printf("T\n");
continue;
}
if( point_in_linesegment(topleft1,topleft2,xstart,ystart,xend,yend) == 1 )
{printf("T\n");
continue;
}
if( point_in_linesegment(bottomright1,bottomright2,xstart,ystart,xend,yend) == 1 )
{printf("T\n");
continue;
}
printf("F\n");
continue;
}/* checked case when line segm is also vertical */
x = topleft1;
y = value_y_given_x(x,xstart, ystart, xend, yend);
if( ( y<= topleft2 && y>= bottomright2 )||( y>= topleft2 && y<= bottomright2 ) )
printf("T\n");
else
printf("F\n");
continue;
}/* VERIFIED when rect is actually a vertical line */
if( (topleft1 != bottomright1) && (topleft2 == bottomright2) )
{/* when rect is actually a horizontal line */
if( ystart == yend)/* line segm is also horiz */
{ if(ystart != topleft2)
{printf("F\n");
continue;
}
if( point_in_linesegment(xstart,ystart,topleft1,topleft2,bottomright1,bottomright2) == 1 )
{printf("T\n");
continue;
}
if( point_in_linesegment(xend,yend,topleft1,topleft2,bottomright1,bottomright2) == 1 )
{printf("T\n");
continue;
}
if( point_in_linesegment(topleft1,topleft2,xstart,ystart,xend,yend) == 1 )
{printf("T\n");
continue;
}
if( point_in_linesegment(bottomright1,bottomright2,xstart,ystart,xend,yend) == 1 )
{printf("T\n");
continue;
}
printf("F\n");
continue;
}/* checked case when line segm is also vertical */
y = topleft2;
x = value_x_given_y(y,xstart, ystart, xend, yend);
/* printf("x = %f y = %f ",x,y); */
if( ( x<= topleft1 && x>= bottomright1 )||( x>= topleft1 && x<= bottomright1 ) )
printf("T\n");
else
printf("F\n");
continue;
}
/* printf(" %d %d %d %d %d %d %d %d",xstart,ystart,xend,yend,x1,y1,x2,y3);exit(1); */
/* now if the line and rectangle are as per convention the prog has reached here */
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 */
{
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 */
printf("T\n");
return;
}/*END of IF #1 */
/* checked when line segment is horizontal */
if(xstart == xend)/* IF #2 *//* the line segm is vertical */
{
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 */
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 if any of the end pt of line segment is inside rectangle */
if( (xstart >= x1)&&(xstart <= x2)&&(ystart >= y3)&&(ystart <= y1) )
{ printf("T\n");
return;
}
if( (xend >= x1)&&(xend <= x2)&&(yend >= y3)&&(yend <= y1) )
{ printf("T\n");
return;
}
/* 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,a1,b1,len;
/* we are assuming that line segm is actually a line */
if( (( x== xend)&&(y == yend) )||( (x == xstart)&&(y == ystart) ) )
return(1);/* 1 means the point is on the line segment */
if( xstart == xend )/* vertical line */
{ if(x != xstart)
return(0);
if( y >= ystart && y <= yend )
return(1);
if( y <= ystart && y >= yend )
return(1);
return(0);
}
if( ystart == yend )/* horizontal line */
{ if(y != ystart)
return(0);
if( x >= xstart && x <= xend )
return(1);
if( x <= xstart && x >= xend )
return(1);
return(0);
}
if(x == xstart && y != ystart)
return(0);
if(x == xend && y != yend)
return(0);
if(x != xstart && y == ystart)
return(0);
if(x != xend && y == yend)
return(0);
a = (y - ystart)/(x - xstart);
b = (y - yend)/(x - xend);
if( a != b)
return(0);
else{
if( (y > ystart && y < yend)||(y < ystart && y > yend) )
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);
}
Posted: Wed Jul 10, 2002 1:46 pm
Why have you commented out the point_in_line_segment checks for checking the top line of the rectangle onwards? This gives wrong answers for several cases.
I can get your previous program accepted with the minimum of changes. You need to be looking at float accuracy: in floats, (a/b)*b != a necessarily, and every time you do a float comparison (a==b) or (a<=b) you are relying on them being more accurate than they actually are. The place where this is really hurting you is in point_in_line_segment.
Mart.
I can get your previous program accepted with the minimum of changes. You need to be looking at float accuracy: in floats, (a/b)*b != a necessarily, and every time you do a float comparison (a==b) or (a<=b) you are relying on them being more accurate than they actually are. The place where this is really hurting you is in point_in_line_segment.
Mart.
Posted: Wed Jul 10, 2002 2:57 pm
i really failed to understand wht u mean by:
Why have you commented out the point_in_line_segment checks for checking the top line of the rectangle onwards? This gives wrong answers for
several cases.
i will have to compare 2 slopes .....what else can i do except comparing 2 floats a,b
Plz help....
Thanks for the patience u r showing with this problem..............
My birthday is coming on 18th JULY....and i will be trying with this problem till this FRI.....if i can't solve this i m not going to celebrate my birthday......
Why have you commented out the point_in_line_segment checks for checking the top line of the rectangle onwards? This gives wrong answers for
several cases.
i will have to compare 2 slopes .....what else can i do except comparing 2 floats a,b
Plz help....
Thanks for the patience u r showing with this problem..............
My birthday is coming on 18th JULY....and i will be trying with this problem till this FRI.....if i can't solve this i m not going to celebrate my birthday......
Posted: Wed Jul 10, 2002 4:15 pm
I was referring to the line:
if( x>=x1 && x<=x2 )
/* && (point_in_linesegment(x,y1,xstart, ystart, xend, yend) == 1) ) */
{ printf("T\n");
return;
}
and similar. I think you need the commented out part in them.
e.g.
1 1 10 10 20 1 80 80
F
I agree you need to compare 2 floats, but it's *how* you're doing it that's wrong. You need to be able to cope with one or other of the floats having an error in accuracy and use a small tolerance (1e-5 is suitable for this problem).
if( x>=x1 && x<=x2 )
/* && (point_in_linesegment(x,y1,xstart, ystart, xend, yend) == 1) ) */
{ printf("T\n");
return;
}
and similar. I think you need the commented out part in them.
e.g.
1 1 10 10 20 1 80 80
F
I agree you need to compare 2 floats, but it's *how* you're doing it that's wrong. You need to be able to cope with one or other of the floats having an error in accuracy and use a small tolerance (1e-5 is suitable for this problem).
Posted: Wed Jul 10, 2002 5:40 pm
I have got my problem ACCEPTED......
Now i m going to celebrate my BIRTHDAY........special invitation to MART....
Thanks man.......
U really showed a great patience........
I didn't applied your method for the function.
... point_in_linesegment()
What i did was to use determinant......its better to do with determinant ...man
Could u please help me with prob 101
posted in the forum on Tue Jul 09, 2002 4:13 pm
Once again thanks .....
Kaushik Acharya
INDIA
Now i m going to celebrate my BIRTHDAY........special invitation to MART....
Thanks man.......
U really showed a great patience........
I didn't applied your method for the function.
... point_in_linesegment()
What i did was to use determinant......its better to do with determinant ...man
Could u please help me with prob 101
posted in the forum on Tue Jul 09, 2002 4:13 pm
Once again thanks .....
Kaushik Acharya
INDIA
Problem 191
Posted: Sat Aug 10, 2002 4:30 pm
I can't find any errors with my code, but it's still getting WA. Are there any big errors?
@begin_of_source_code
/* @JUDGE_ID: 17030CW 191 C++ */
#include <stdio.h>
#include <stdlib.h>
struct point {
int x, y;
point(int a=0, int b=0) { x=a; y=b; }
};
int cross(point a, point b) {
return (a.x*b.y-a.y*b.x);
}
point from(point a, point b) {
return point(b.x-a.x, b.y-a.y);
}
bool intersect(point a, point b, point c, point d) {
int t1, t2;
t1 = cross(from(a, b), from(a, c));
t2 = cross(from(a, b), from(a, d));
if (t1*t2>0) return 0;
t1 = cross(from(c, a), from(c, d));
t2 = cross(from(c, b), from(c, d));
if (t1*t2>0) return 0;
return 1;
}
bool inside(point a, point b, point c) {
return ((a.x-b.x)*(a.x-c.x)<=0 && (a.y-b.y)*(a.y-c.y)<=0);
}
void getpoint(point &a) {
scanf("%d%d", &a.x, &a.y);
}
void swap(int &a, int &b) {
int temp = a; a = b; b = temp;
}
int main() {
int a, b;
int times;
point start, end, p1, p2, p3, p4;
scanf("%d", ×);
for (a = 0; a < times; a++) {
getpoint(start);
getpoint(end);
getpoint(p1);
getpoint(p3);
p2 = point(p1.x, p3.y);
p4 = point(p3.x, p1.y);
if (start.x == end.x && start.y == end.y) {
if (inside(start, p1, p3))
printf("T\n");
else
printf("F\n");
}
else if (p1.x == p3.x && p1.y == p3.y) {
if (inside(p1, start, end) && cross(from(start, p1), from(start, end)) ==
0)
printf("T\n");
else
printf("F\n");
}
else if (intersect(start, end, p1, p2) ||
intersect(start, end, p2, p3) ||
intersect(start, end, p3, p4) ||
intersect(start, end, p4, p1) ||
inside(start, p1, p3) ||
inside(end, p1, p3))
printf("T\n");
else printf("F\n");
}
return 0;
}
@end_of_source_code
Thanks for any help.
@begin_of_source_code
/* @JUDGE_ID: 17030CW 191 C++ */
#include <stdio.h>
#include <stdlib.h>
struct point {
int x, y;
point(int a=0, int b=0) { x=a; y=b; }
};
int cross(point a, point b) {
return (a.x*b.y-a.y*b.x);
}
point from(point a, point b) {
return point(b.x-a.x, b.y-a.y);
}
bool intersect(point a, point b, point c, point d) {
int t1, t2;
t1 = cross(from(a, b), from(a, c));
t2 = cross(from(a, b), from(a, d));
if (t1*t2>0) return 0;
t1 = cross(from(c, a), from(c, d));
t2 = cross(from(c, b), from(c, d));
if (t1*t2>0) return 0;
return 1;
}
bool inside(point a, point b, point c) {
return ((a.x-b.x)*(a.x-c.x)<=0 && (a.y-b.y)*(a.y-c.y)<=0);
}
void getpoint(point &a) {
scanf("%d%d", &a.x, &a.y);
}
void swap(int &a, int &b) {
int temp = a; a = b; b = temp;
}
int main() {
int a, b;
int times;
point start, end, p1, p2, p3, p4;
scanf("%d", ×);
for (a = 0; a < times; a++) {
getpoint(start);
getpoint(end);
getpoint(p1);
getpoint(p3);
p2 = point(p1.x, p3.y);
p4 = point(p3.x, p1.y);
if (start.x == end.x && start.y == end.y) {
if (inside(start, p1, p3))
printf("T\n");
else
printf("F\n");
}
else if (p1.x == p3.x && p1.y == p3.y) {
if (inside(p1, start, end) && cross(from(start, p1), from(start, end)) ==
0)
printf("T\n");
else
printf("F\n");
}
else if (intersect(start, end, p1, p2) ||
intersect(start, end, p2, p3) ||
intersect(start, end, p3, p4) ||
intersect(start, end, p4, p1) ||
inside(start, p1, p3) ||
inside(end, p1, p3))
printf("T\n");
else printf("F\n");
}
return 0;
}
@end_of_source_code
Thanks for any help.