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

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

Post by Mart »

How about:

4 9 11 2 12 5 1 5
4 9 11 2 4 9 4 9

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

Post by taj79 »

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

These are not rectangle.
Top
10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:
Contact 10153EN

Post by 10153EN »

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 :)
Top
taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:
Contact taj79

Post by taj79 »

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);
}
Top
Mart
New poster
Posts: 18
Joined: Wed Jun 12, 2002 1:00 pm

Post by Mart »

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.
Top
taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:
Contact taj79

Post by taj79 »

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);
}
Top
Mart
New poster
Posts: 18
Joined: Wed Jun 12, 2002 1:00 pm

Post by Mart »

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.
Top
taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:
Contact taj79

Post by taj79 »

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);
}
Top
Mart
New poster
Posts: 18
Joined: Wed Jun 12, 2002 1:00 pm

Post by Mart »

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.
Top
taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:
Contact taj79

Post by taj79 »

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);
}
Top
Mart
New poster
Posts: 18
Joined: Wed Jun 12, 2002 1:00 pm

Post by Mart »

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.
Top
taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:
Contact taj79

Post by taj79 »

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......
Top
Mart
New poster
Posts: 18
Joined: Wed Jun 12, 2002 1:00 pm

Post by Mart »

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).
Top
taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:
Contact taj79

Post by taj79 »

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
Top
bjacoke001
New poster
Posts: 6
Joined: Fri Jul 26, 2002 6:42 pm

Problem 191

Post by bjacoke001 »

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.
Top
Post Reply

Return to “Volume 1 (100-199)”