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

Mart
New poster
Posts: 18
Joined: Wed Jun 12, 2002 1:00 pm

Post by Mart » 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

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

Post by taj79 » Mon Jul 08, 2002 3:28 pm

The 1st one is a line
& 2nd one is a point

These are not rectangle.

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 10153EN » 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 :)

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

Post by taj79 » Mon Jul 08, 2002 5:59 pm

i cosidered special cases but got WA
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",&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;
         }
  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);
}


Mart
New poster
Posts: 18
Joined: Wed Jun 12, 2002 1:00 pm

Post by Mart » 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.

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

Post by taj79 » 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",&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;
         }
  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);
}


Mart
New poster
Posts: 18
Joined: Wed Jun 12, 2002 1:00 pm

Post by Mart » 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.

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

Post by taj79 » 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",&yend);
    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);
}


Mart
New poster
Posts: 18
Joined: Wed Jun 12, 2002 1:00 pm

Post by Mart » 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.

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

Post by taj79 » 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",&yend);
    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);
}

  

Mart
New poster
Posts: 18
Joined: Wed Jun 12, 2002 1:00 pm

Post by Mart » 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.

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

Post by taj79 » 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......

Mart
New poster
Posts: 18
Joined: Wed Jun 12, 2002 1:00 pm

Post by Mart » 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).

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

Post by taj79 » 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

bjacoke001
New poster
Posts: 6
Joined: Fri Jul 26, 2002 6:42 pm

Problem 191

Post by bjacoke001 » 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", &times);
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.

Post Reply

Return to “Volume 1 (100-199)”