191 - Intersection

[10153EN]

Please read more carefully on the input description of the problem. You have some assumption~

[tam]

The Question Said "The terms and do not imply any ordering of coordinates. " .
I don't know what is it about ...........
( I don't understand .... what is the error for the input........)
Sorry.

If I paste the code,

[pascal]

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

Still Get Wrong Answer.
[/pascal]

[Mart]

Firstly, you need that extra code.
Secondly, strange to go with x1<=x2 but y1>=y2, it's bound to cause confusion in your maths, but whatever.
Thirdly, try:

1
4 9 4 7 1 5 7 1

correct output:
F

[taj79]

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

Please explain with some example.

[Adrian Kuegel]

The input can contain coordinates with left>right and/or bottom>top. You have to swap the values, so that left<right and bottom<top.
Example:
4 9 11 2 7 1 1 5
process with:
4 9 11 2 1 5 7 1

[taj79]

But it is certain( i suppose) that the 5th and 7th elements in a line of input are the x coordinates of top left & bottom right( not necessarily in order)
and similarly 6th and 8th element are y coordinates.

Am i correct

[Mart]

You are correct.

[taj79]

Judge is giving wrong answer for my prog but i m unable to find a single case where my prog is giving wrong answer.
Can u help me out?

Code: Select all

#include<stdio.h>

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

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

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


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

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

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

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

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


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

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

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

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

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

}

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

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

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

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

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


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

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

[Mart]

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

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

Mart

[taj79]

I have changed it to

Code: Select all

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

Still judge gives wrong answer.
my rectangle is

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

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


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

[Revenger]

I can't understand why my program gets WA:

[pascal]Program p191;

Const Eps = 1e-7;

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

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

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

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

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

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

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

[Revenger]

I found some mistakes, but still WA

[pascal]Program p191;

Const Eps = 1e-7;

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

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

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

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

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

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

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

[Mart]

You still fail the case:
4 9 4 7 1 5 7 1
which should return F

In your code:
It can fail for topleft1==bottomright1 or topleft2==bottomright2

You have some ambigious IF IF ELSE statements.

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

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

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

Don't be sorry - I was just being cheeky

Mart

[Revenger]

I get Accepted at last!

[taj79]

again WA...had i left any case this time also? ...Plz help

Code: Select all

#include<stdio.h>

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

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

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

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

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

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

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

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

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

   printf("T\n");
    return;

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

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

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

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

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

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

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


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

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

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

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

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

}

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

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

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

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

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


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

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