Posted: Tue Jul 02, 2002 7:24 am
Please read more carefully on the input description of the problem. You have some assumption~ 

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",¥d);
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);
}
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;
}
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",¥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;
}
/* 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);
}