191 - Intersection

[daveon]

Hi,

Your code fails this IO:

Code: Select all

input:
1
4 9 11 2 1 1 7 5

output:
F

[raygunx]

I test many groups of I/O but I still get WA in this problem.
Why? (under this line is my code.)


#include<iostream.h>


int main()
{
int n;
double x1,y1,x2,y2;
double sqx1,sqy1,sqx2,sqy2,temp;
double a,b;
double sx,sy,sxx,syy;
cin>>n;
while(n--)
{
cin>>x1>>y1>>x2>>y2>>sqx1>>sqy1>>sqx2>>sqy2;
if(sqx1>sqx2){temp=sqx1;sqx1=sqx2;sqx2=temp;}
if(sqy1>sqy2){temp=sqy1;sqy1=sqy2;sqy2=temp;}
if(x1==x2)
{
if(x1>x2){temp=x1;x1=x2;x2=temp;}
if(y1>y2){temp=y1;y1=y2;y2=temp;}
if(x1>=sqx1&&x2<=sqx2&&y1>=sqy1&&y2<=sqy2){cout<<"T"<<endl;}
else if(x1>=sqx1&&x2<=sqx2&&y1==sqy2){cout<<"T"<<endl;}
else if(x1>=sqx1&&x2<=sqx2&&y2==sqy1){cout<<"T"<<endl;}
else{cout<<"F"<<endl;}
}
else
{
a=(y1-y2)/(x1-x2);
b=y1-a*x1;
sy=a*sqx1+b;
syy=a*sqx2+b;
sx=(sqy1-b)/a;
sxx=(sqy2-b)/a;
if(x1>x2){temp=x1;x1=x2;x2=temp;}
if(y1>y2){temp=y1;y1=y2;y2=temp;}
if(sy>=y1&&sy<=y2&&sy>=sqy1&&sy<=sqy2){cout<<"T"<<endl;}
else if(syy>=y1&&syy<=y2&&syy>=sqy1&&syy<=sqy2){cout<<"T"<<endl;}
else if(sx>=x1&&sx<=x2&&sx>=sqx1&&sx<=sqx2){cout<<"T"<<endl;}
else if(sxx>=x1&&sxx<=x2&&sxx>=sqx1&&sxx<=sqx2){cout<<"T"<<endl;}
else if(x1>=sqx1&&x2<=sqx2&&y1>=sqy1&&y2<=sqy2){cout<<"T"<<endl;}
else{cout<<"F"<<endl;}
}
}
}


Could somebody tell me why I get WA? Thank you very much!

[tan_Yui]

Hi.
Can your code produce correct output when a==0 or x1==x2 ?
Please check again about that case with the input written on the following thread.
http://online-judge.uva.es/board/viewto ... hlight=191

Best regards.

[maxbcr2000]

My code(C++):
#include <iostream.h>
int dd(int,int,int,int,int,int,int,int);
void main()
{
int n,i,x1,y1,x2,y2,sx1,sy1,sx2,sy2,lx,ly,rx,ry;
cin>>n;
for (i=0;i<n;i++)
{
cin>>x1>>y1>>x2>>y2>>sx1>>sy1>>sx2>>sy2;
lx=sx1;ly=sy1;rx=sx2;ry=sy2;
if (lx>rx) {lx=sx2;rx=sx1;}
if (ly<ry) {ly=sy2;ry=sy1;}
int checku,checkd,checkl,checkr,checku2,checkd2,checkl2,checkr2;
checkd=dd(x1,y1,x2,y2,lx,ry,rx,ry);
checkd2=dd(lx,ry,rx,ry,x1,y1,x2,y2);
checku=dd(x1,y1,x2,y2,lx,ly,rx,ly);
checku2=dd(lx,ly,rx,ly,x1,y1,x2,y2);
checkl=dd(x1,y1,x2,y2,lx,ly,lx,ry);
checkl2=dd(lx,ly,lx,ry,x1,y1,x2,y2);
checkr=dd(x1,y1,x2,y2,rx,ly,rx,ry);
checkr2=dd(rx,ly,rx,ry,x1,y1,x2,y2);
if (checku==1 || checkd==1 || checkl==1 || checkr==1) cout<<"T"<<endl;
else if ((checku==2 && checku2==2)|| (checkd==2 && checkd2==2) || (checkl==2 && checkl2==2)|| (checkr==2 && checkr2==2)) cout<<"T"<<endl;
else if (x1<=rx && x1>=lx && x2<=rx && x2>=lx && y1<=ly && y1>=ry && y2<=ly && y2>=ry) cout<<"T"<<endl;
else cout<<"F"<<endl;

}

}

int dd(int x1,int y1,int x2,int y2,int lx,int ly,int rx,int ry)
{
int a,b;
if ((lx-x1)*(y1-y2)-(x1-x2)*(ly-y1)==0) a=0;
else if((lx-x1)*(y1-y2)-(x1-x2)*(ly-y1)>0) a=1;
else a=-1;
if ((rx-x1)*(y1-y2)-(x1-x2)*(ry-y1)==0) b=0;
else if((rx-x1)*(y1-y2)-(x1-x2)*(ry-y1)>0) b=1;
else b=-1;
if (a==0 || b==0) return 1;
if (a!=b) return 2;
else return 0;
}

[handsomepot]

WHY WA
#include<iostream>
using namespace std;
int main()
{
int num;
bool intersect = false;
int t1,t2;
int xstart,ystart,xend,yend,xleft,ytop,xright,ybottom;
int a,b,c,d;
cin >> num;
while(cin>>xstart>>ystart>>xend>>yend>>xleft>>ytop>>xright>>ybottom)
{
a = xright;
b = ytop;
c = xleft;
d = ybottom;


if(xleft>xright)
{
t1 = xleft;
xleft = xright;
xright = t1;
}
if(ytop<ybottom)
{
t1 = ytop;
ytop = ybottom;
ybottom = t1;
}

if(((xstart>=xleft&&xstart<=xright)&&(ystart>=ybottom&&ystart<=ytop))||((xend>=xleft&&xend<=xright)&&(yend>=ybottom&&yend<=ytop)))
{
if(!intersect)
{
cout << "T\n";

intersect = true;
}
}
else
{
if((xstart-a)*(yend-b)-(ystart-b)*(xend-a)>0)
if((xstart-xright)*(yend-ybottom)-(ystart-ybottom)*(xend-xright)>0)
if((xstart-c)*(yend-d)-(ystart-d)*(xend-c)>0)
if((xstart-xleft)*(yend-ytop)-(ystart-ytop)*(xend-xleft)>0)
{
if(!intersect)
cout << "F\n";
intersect = true;
}

if((xstart-a)*(yend-b)-(ystart-b)*(xend-a)<0)
if((xstart-xright)*(yend-ybottom)-(ystart-ybottom)*(xend-xright)<0)
if((xstart-c)*(yend-d)-(ystart-d)*(xend-c)<0)
if((xstart-xleft)*(yend-ytop)-(ystart-ytop)*(xend-xleft)<0)
{
if(!intersect)
cout << "F\n";
intersect = true;
}
if(!intersect)
cout << "T\n";
intersect = true;
}

intersect = false;

}
return 0;
}

[mmonish]

Search the board first. Don't open a new thread. Better use this

http://online-judge.uva.es/board/viewto ... hlight=191
http://online-judge.uva.es/board/viewto ... hlight=191

[dadai]

I had tried many samples,
but I still can not find where the wrong is.
Can someone tell me?
Thanks

this is my code:

#include <stdio.h>

int poly_a, poly_b, poly_c;

int x_is_cross(int y, int x1, int x2)
{
float tmp=0;
tmp = (float) (poly_c-poly_b*y)/poly_a;
if(tmp >= x1 && tmp <= x2)
return 1;
return 0;
}

int y_is_cross(int x, int y1, int y2)
{
float tmp=0;
tmp = (float) (poly_c-poly_a*x)/poly_b;
if(tmp >= y1 && tmp <= y2)
return 1;
return 0;
}

int is_in(int a, int b, int c, int d,
int x1, int x2, int y1, int y2)
{
if(a > x1 && a < x2) {
if(b > y1 && b < y2)
return 1;
}
if(c > x1 && c < x2) {
if(d > y1 && d < y2)
return 1;
}
return 0;
}

int main()
{
int n=0;
int tmp1=0, tmp2=0, tmp3=0, tmp4=0;
int swap_tmp=0;
int x1=0, x2=0, y1=0, y2=0;

scanf("%d", &n);
while(n--) {
scanf("%d %d %d %d %d %d %d %d",
&tmp1, &tmp2, &tmp3, &tmp4, &x1, &y1, &x2, &y2);

if(x1 > x2) {
swap_tmp = x1;
x1 = x2;
x2 = swap_tmp;
}
if(y1 > y2) {
swap_tmp = y1;
y1 = y2;
y2 = swap_tmp;
}

poly_b = tmp3-tmp1;
poly_a = tmp4-tmp2;
poly_c = poly_a*tmp1 + poly_b*tmp2;

if(x_is_cross(y1, x1, x2)) {
printf("T\n");
continue;
}
if(x_is_cross(y2, x1, x2)) {
printf("T\n");
continue;
}
if(y_is_cross(x1, y1, y2)) {
printf("T\n");
continue;
}
if(y_is_cross(x2, y1, y2)) {
printf("T\n");
continue;
}
if(is_in(tmp1, tmp2, tmp3, tmp4, x1, x2, y1, y2)) {
printf("T\n");
continue;
}
printf("F\n");
}

return 0;
}

[dadai]

I found some mistakes in last code,
and I modified it yet.

I follow the page
http://online-judge.uva.es/board/viewto ... hlight=191
and try many examples,
every examples I tried is correct.
But when I update the code to web,
I still get "Wrong answer".

Do someone know where's the problem I make?
I tried this question for many days.... >"<



#include <stdio.h>

int poly_a, poly_b, poly_c;
int tmp1, tmp2, tmp3, tmp4;

int x_is_cross(int y, int x1, int x2)
{
float tmp=0;
tmp = (float) (poly_c-poly_b*y)/poly_a;
// printf("x_is_cross: %f %d %d\n", tmp, tmp1, tmp3);
if((tmp >= tmp1 || tmp >= tmp3) && (tmp >= x1))
if((tmp <= tmp1 || tmp <= tmp3) && (tmp <= x2))
return 1;
return 0;
}

int y_is_cross(int x, int y1, int y2)
{
float tmp=0;
tmp = (float) (poly_c-poly_a*x)/poly_b;
// printf("y_is_cross: %f %d %d\n", tmp, tmp2, tmp4);
if((tmp >= tmp2 || tmp >= tmp4) && (tmp >= y1))
if((tmp <= tmp2 || tmp <= tmp4) && (tmp <= y2))
return 1;
return 0;
}

int is_in(int x1, int x2, int y1, int y2)
{
if(tmp1 > x1 && tmp1 < x2) {
if(tmp2 > y1 && tmp2 < y2)
return 1;
}
if(tmp3 > x1 && tmp3 < x2) {
if(tmp4 > y1 && tmp4 < y2)
return 1;
}
return 0;
}

int main()
{
int n=0;
int swap_tmp=0;
int x1=0, x2=0, y1=0, y2=0;

scanf("%d", &n);
while(n--) {
scanf("%d %d %d %d %d %d %d %d",
&tmp1, &tmp2, &tmp3, &tmp4, &x1, &y1, &x2, &y2);

if(x1 > x2) {
swap_tmp = x1;
x1 = x2;
x2 = swap_tmp;
}
if(y1 > y2) {
swap_tmp = y1;
y1 = y2;
y2 = swap_tmp;
}

poly_b = tmp1-tmp3;
poly_a = tmp4-tmp2;
poly_c = poly_a*tmp1 + poly_b*tmp2;
// printf("poly: (%d)x+(%d)y = %d\n", poly_a, poly_b, poly_c);

if(x_is_cross(y1, x1, x2)) {
printf("T\n");
continue;
}
if(x_is_cross(y2, x1, x2)) {
printf("T\n");
continue;
}
if(y_is_cross(x1, y1, y2)) {
printf("T\n");
continue;
}
if(y_is_cross(x2, y1, y2)) {
printf("T\n");
continue;
}
if(is_in(x1, x2, y1, y2)) {
printf("T\n");
continue;
}
printf("F\n");
}

return 0;
}

[maruf]

code removed

[NiazKhan]

Here's the sample input

Code: Select all

68 
4 9 11 2 1 1 7 5 
11 2 4 9 1 1 7 5 
12 12 24 24 19 5 25 17 
4 6 15 9 1 1 11 11 
19 5 25 17 12 12 24 24 
0 18 8 12 1 1 11 11 
2 4 4 2 1 1 11 11 
-4 9 -11 2 -1 1 -7 5 
-11 2 -4 9 -1 1 -7 5 
-12 12 -24 24 -19 5 -25 17 
-4 6 -15 9 -1 1 -11 11 
-19 5 -25 17 -12 12 -24 24 
0 18 -8 12 -1 1 -11 11 
-2 4 -4 2 -1 1 -11 11 
4 -9 11 -2 1 -1 7 -5 
11 -2 4 -9 1 -1 7 -5 
12 -12 24 -24 19 -5 25 -17 
4 -6 15 -9 1 -1 11 -11 
19 -5 25 -17 12 -12 24 -24 
0 -18 8 -12 1 -1 11 -11 
2 -4 4 -2 1 -1 11 -11 
-4 -9 -11 -2 -1 -1 -7 -5 
-11 -2 -4 -9 -1 -1 -7 -5 
-12 -12 -24 -24 -19 -5 -25 -17 
-4 -6 -15 -9 -1 -1 -11 -11 
-19 -5 -25 -17 -12 -12 -24 -24 
0 -18 -8 -12 -1 -1 -11 -11 
-2 -4 -4 -2 -1 -1 -11 -11 
9 1 9 2 4 3 9 6 
9 2 9 1 4 3 9 6 
10 3 13 3 4 3 9 6 
13 3 10 3 4 3 9 6 
10 6 14 6 4 3 9 6 
14 6 10 6 4 3 9 6 
9 7 9 10 4 3 9 6 
9 10 9 7 4 3 9 6 
4 7 4 10 4 3 9 6 
4 10 4 7 4 3 9 6 
0 6 3 6 4 3 9 6 
3 6 0 6 4 3 9 6 
1 3 3 3 4 3 9 6 
3 3 1 3 4 3 9 6 
4 0 4 2 4 3 9 6 
4 2 4 0 4 3 9 6 
5 3 8 5 4 3 9 6 
8 5 5 3 4 3 9 6 
5 3 8 3 4 3 9 6 
8 3 5 3 4 3 9 6 
6 4 6 5 4 3 9 6 
6 5 6 4 4 3 9 6 
4 3 9 6 4 3 9 6 
9 6 4 3 4 3 9 6 
4 3 5 4 4 3 9 6 
5 4 4 3 4 3 9 6 
5 3 8 3 4 3 9 6 
8 3 5 3 4 3 9 6 
5 3 9 3 4 3 9 6 
9 3 5 3 4 3 9 6 
4 4 4 5 4 3 9 6 
4 5 4 4 4 3 9 6 
4 3 4 5 4 3 9 6 
4 5 4 3 4 3 9 6 
4 3 4 6 4 3 9 6 
4 6 4 3 4 3 9 6 
9 2 9 5 4 3 9 6 
9 5 9 2 4 3 9 6 
9 2 9 7 4 3 9 6 
9 7 9 2 4 3 9 6

And the Output will be

Code: Select all

F 
F 
F 
T 
T 
F 
T 
F 
F 
F 
T 
T 
F 
T 
F 
F 
F 
T 
T 
F 
T 
F 
F 
F 
T 
T 
F 
T 
F 
F 
F 
F 
F 
F 
F 
F 
F 
F 
F 
F 
F 
F 
F 
F 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 
T 

i don't understand why for the input: 0 18 8 12 1 1 11 11
outout is: F
coz the eqn of the line is
3x+4y=72
and (11,9.75) is a point on that line
and (11,9.75) is also a point on the rectangle.
so the ans should be T i think.
please explain me about my mistake.
thank u.

[Shafaet_du]

The tricky part is bottom and up are not always bottom and up .

@Niaz: You dont need to make any equation and do calculation using floating point number. There is a good algo to find segment intersection,check coreman's intro to algorithm book(computation geometry section).

[S.H.Bouwhuis]

I have found 74 different inputs here on the boards, and all of them are correct for my program. Unfortunately, I still get WA.

Could someone with AC please try the following inputs?

Code: Select all

500
-5 4 -3 3 4 1 -2 -4
-2 0 2 4 0 0 -1 1
1 -3 -8 -6 -3 3 3 -4
-8 -3 10 1 -5 5 3 0
0 -1 -8 -7 3 0 1 2
0 -2 -2 7 -1 0 -4 -2
-5 10 1 7 -5 3 3 0
0 9 8 -5 -1 1 -1 -1
0 0 1 4 4 0 3 -2
-3 3 7 -1 -1 -1 4 -1
2 -6 -10 -4 3 -1 -3 4
-3 3 -5 -2 -5 2 -2 -1
-2 1 0 -7 4 4 0 5
-5 9 6 1 -1 -2 0 -5
8 9 8 8 1 -2 -3 1
0 -9 0 -8 5 5 3 5
7 -3 3 -7 3 3 4 5
-8 10 -4 -5 -4 -2 -1 -5
5 -3 7 -2 -3 1 5 4
-9 -9 -8 -7 2 -4 5 -5
-6 -3 8 5 -5 0 -5 1
-1 7 -4 -6 5 0 4 2
6 1 4 -1 0 -2 -4 0
2 -7 0 7 0 2 4 0
3 -8 9 4 5 0 0 0
6 2 -3 -9 -4 -5 -1 -1
0 -4 -7 0 3 4 -4 -3
-1 -10 6 5 3 0 -3 0
-7 -7 7 -3 1 5 2 -4
8 -4 -8 -1 -4 5 4 5
-7 -9 -8 7 5 -2 5 4
2 -5 -10 3 -1 0 2 -3
3 -10 1 8 -5 1 2 -4
-6 -6 6 1 1 1 5 4
-1 8 -9 6 -5 0 2 5
-7 0 1 -9 -3 -2 -2 -4
10 -9 10 -3 1 1 1 5
2 1 -8 9 1 5 -2 -3
-2 0 8 2 1 -4 4 -1
-1 -8 7 -4 5 -4 4 -5
-3 4 -6 -10 -5 5 1 -1
5 -2 0 -2 2 -2 -5 3
-3 2 -8 -6 -1 4 -1 -2
1 5 5 1 4 -2 -5 2
0 -4 8 7 5 3 -5 -3
-8 -5 -2 0 5 2 -1 0
10 -9 10 -4 1 -3 1 -5
1 2 6 -2 5 4 5 3
-1 6 -10 3 5 -3 1 -2
9 10 -9 -2 0 1 0 4
-10 3 3 3 5 -5 1 5
-4 6 0 10 3 0 5 -2
-6 -8 -1 -3 -5 -5 -3 2
-6 1 4 1 5 1 -5 -1
3 2 -6 0 2 -4 5 -2
-3 -8 8 5 0 5 4 0
10 -4 -10 -4 -5 3 3 5
1 -10 -4 5 5 2 3 -4
3 3 4 5 0 4 3 0
0 3 1 3 -5 1 -2 -3
-3 -9 -9 4 1 5 -1 -4
-7 -8 -7 -5 3 5 -5 1
-5 -2 -7 -8 -4 -1 3 -3
6 -6 1 8 -2 1 1 5
5 10 8 0 1 1 -4 -5
-8 6 7 3 2 -4 0 -5
8 7 6 4 4 1 -3 -1
-7 -1 8 -6 5 4 4 -3
8 4 -2 -8 -4 1 0 -2
-3 -3 -9 7 5 5 0 0
1 -5 -9 -4 5 -1 1 1
6 -4 -3 3 -4 4 -3 5
-1 7 -7 9 3 0 0 -5
0 -1 1 -2 -1 -5 1 -2
-1 9 -1 6 -5 5 2 3
1 -5 4 -10 -1 0 1 2
-2 -3 -10 -10 3 0 0 4
10 -9 7 -2 -1 -5 -2 5
-5 1 -7 -7 3 1 -4 -3
4 4 -3 -7 1 5 4 0
5 8 6 -8 4 3 -3 -2
-10 1 6 2 0 5 4 -3
-6 -10 -9 2 3 3 4 -2
-2 9 5 8 2 1 -1 -4
10 -5 -6 6 -4 4 -5 5
4 -7 -5 -10 1 2 -2 1
-4 -7 10 9 -1 -5 4 4
7 -9 4 -10 4 -5 3 1
-2 0 -10 -9 -2 4 -3 1
7 9 4 1 5 0 -3 5
1 3 -5 6 -2 -1 2 0
5 -8 -9 -7 -4 -4 -3 1
-10 5 -3 -8 -3 -5 4 -1
3 -3 7 8 1 2 5 0
-2 0 -3 -8 0 4 3 -1
-6 -4 0 8 2 0 -1 -5
2 10 3 8 -3 4 -2 -5
-4 -1 7 -5 4 -5 -2 5
-7 -5 -3 -5 -4 5 2 -3
-4 3 -8 4 4 5 3 5
9 -4 7 6 0 3 -5 4
-8 -5 10 -3 -2 -1 2 -4
2 0 -1 -5 -3 -2 -4 0
6 -6 -1 4 -3 3 0 2
9 6 -6 1 -1 -3 1 5
-3 7 4 -7 -4 2 5 -4
6 3 7 10 -1 1 3 3
3 -5 8 3 1 3 1 1
9 2 -6 -5 0 -1 -3 -4
-8 2 -9 -10 2 -4 5 -2
-7 -3 8 -6 -1 4 0 -4
0 -8 -9 -7 -4 3 0 -5
-8 8 3 5 5 0 4 5
-6 8 -1 7 -4 0 3 1
2 4 -5 2 -4 -4 2 0
2 4 -1 -7 -5 -1 3 0
-4 -2 -8 2 -2 -3 -5 -5
-4 7 7 8 -2 -5 4 2
6 8 5 7 0 0 -4 -1
6 -1 9 -9 -4 4 3 -3
-5 9 -1 -4 2 -1 -1 1
-8 9 -6 -5 -1 4 5 3
-4 -6 0 1 4 -2 1 1
0 4 4 -5 -4 -3 -4 4
-2 6 2 8 2 -5 -3 -2
-8 -3 6 -2 -1 3 -4 -5
-9 -7 5 0 -2 3 -5 3
7 -3 -3 9 3 -4 5 3
7 -7 0 -9 2 4 -3 -5
3 -2 -2 3 -2 1 -1 -2
-6 -2 2 7 -4 5 0 2
-5 3 -10 8 3 -4 -1 1
0 6 0 8 1 4 -1 -3
0 6 7 7 1 5 4 5
-6 5 -7 6 -2 -5 -3 4
-1 -5 -3 4 0 3 0 -1
-2 8 -5 -6 -3 1 2 -3
-5 -5 -1 -7 -5 3 1 -2
0 -8 -7 -10 -4 0 -5 5
6 8 -2 9 -3 -1 3 1
-2 2 3 5 -3 2 -3 -2
-2 -2 -9 10 0 -2 3 0
2 -6 6 -9 4 -1 1 -4
-5 10 -9 5 -2 1 -1 1
-6 -8 -4 3 -3 1 -4 -3
-8 10 5 7 3 2 3 -4
-3 4 5 -2 0 0 -1 -1
10 5 -8 -6 4 -1 2 0
2 -7 7 -2 1 5 -5 4
-1 -1 -3 -1 0 2 1 4
0 -5 -3 8 -1 4 -1 -4
3 6 3 5 1 1 0 -1
4 -5 -7 -1 -1 0 -1 -2
-3 -5 -8 0 -4 -3 2 0
-10 2 7 7 -5 3 -5 -4
-1 -7 6 -2 -1 5 3 4
10 -5 -1 -5 0 -5 -1 0
-7 -2 1 -8 2 5 -3 5
-6 -6 8 -7 3 5 -4 -3
-8 9 -8 9 -3 1 0 5
4 5 9 9 -1 3 -4 -2
4 -2 -10 -3 -1 0 4 5
-2 -4 5 2 2 3 0 1
-3 0 -3 -10 -4 4 1 3
3 -9 6 10 -4 4 2 4
6 7 4 6 5 -3 5 1
-7 5 -9 -9 0 0 -3 -3
4 -5 -3 3 -2 -2 0 -3
9 1 -2 -4 -4 4 -5 3
-9 6 -8 -1 -2 4 2 4
6 -8 -8 -2 4 0 5 5
10 -2 -9 -4 -3 1 0 2
-8 3 -7 -1 4 3 3 1
-2 -9 4 -1 3 -3 2 4
6 -6 -5 8 4 -1 0 -3
8 -10 -1 -5 4 -3 -5 -4
5 -3 2 8 -3 0 -3 4
10 2 4 3 -1 -3 0 -3
0 6 0 -10 -5 -1 0 -3
5 -9 0 -7 -3 -4 1 -1
3 -6 -8 -6 2 -5 3 5
-1 5 8 4 -1 -3 0 -1
-5 -2 8 3 3 5 -1 3
-10 9 8 8 5 -3 -3 3
-1 -6 -5 -1 -4 4 2 -2
6 10 -1 -9 -3 -2 1 5
-1 -7 8 -6 3 -1 -3 -4
-5 7 9 6 5 3 1 2
2 4 -1 4 0 0 5 -3
-10 -6 0 -8 -4 0 -4 -5
-8 8 -6 -3 -2 5 -3 3
9 0 -2 -8 -3 3 2 -5
-4 5 -6 10 3 1 -4 0
9 -2 -2 -7 -4 -1 -2 -1
3 -9 -10 -5 1 -3 -2 0
4 -9 0 -4 -4 0 3 1
-5 -9 -6 7 -5 3 -3 3
2 10 5 4 1 -4 1 -2
-3 9 -9 4 -3 -3 1 -2
4 -2 -6 -1 5 0 5 0
-4 -2 -9 9 0 -3 1 -1
-10 -7 -8 2 5 -4 5 -3
10 -4 -10 7 -2 -2 -5 -1
-3 7 7 -2 -3 2 -1 -4
9 -5 5 0 -4 0 -5 -3
-3 6 7 1 3 -2 -2 2
-3 -8 -3 -3 -3 0 -2 3
-5 3 9 1 3 -3 0 -4
7 -2 -7 2 -2 3 1 -3
-10 9 -7 6 -3 4 -3 0
10 -4 9 2 -2 5 4 -5
-10 2 -9 4 1 4 0 5
5 -1 -10 -10 -5 2 -4 -3
-3 -2 -4 -2 -5 -5 5 -3
1 10 -4 -9 3 -4 4 -3
3 -2 0 -8 4 -2 -1 -3
-10 1 1 -3 -1 3 5 3
3 2 -7 -9 4 -3 -2 -3
-6 4 7 10 0 -3 5 -4
5 -9 -8 1 0 4 -2 4
-1 -10 -8 8 -3 -1 -5 0
8 -6 -8 -9 3 -2 5 5
-5 2 0 -8 -2 -2 0 -5
-5 -1 10 0 -4 1 -1 4
-4 4 -6 -3 0 0 -5 -3
2 4 0 6 5 0 2 3
-10 -4 2 -8 2 0 -4 5
-8 0 3 9 -2 2 5 0
1 3 -2 -7 -5 2 3 -2
-4 0 0 -8 0 1 4 1
-3 7 0 -8 2 -1 1 -4
7 -3 4 -1 1 -5 -5 1
7 -4 -8 -8 -3 -2 -2 -5
8 6 1 9 -3 3 -1 -3
-9 2 8 0 4 -2 1 -4
-8 1 3 8 2 0 -4 -1
-4 -8 10 3 2 2 -3 2
8 -3 1 1 -4 0 -1 5
2 -5 3 -2 -5 -2 -3 1
2 -6 -3 -3 4 1 -4 -1
3 7 -8 0 1 -3 4 -2
1 9 7 8 -3 1 -1 -5
-4 -1 -1 -5 3 -5 -3 4
6 -2 6 10 1 5 2 3
-6 0 8 -7 4 -3 -4 0
-2 5 -7 -5 -2 5 1 -1
9 0 9 -4 2 2 5 -4
10 -1 -4 5 2 -4 -2 -5
10 -3 9 -9 3 4 -3 0
1 -5 4 -4 5 5 5 5
-10 4 9 10 3 0 2 2
6 9 1 9 5 -2 2 -4
-9 0 9 9 -2 2 -4 5
4 -2 -9 -9 -4 0 -4 4
3 -9 2 6 4 -3 5 -1
9 -10 -9 1 -5 4 0 -1
1 6 -10 -6 -3 3 -4 -2
-7 0 3 0 -5 4 -2 -5
3 7 9 -8 1 3 5 1
7 5 5 2 2 2 2 -4
-3 -2 9 0 3 0 -4 1
9 1 9 2 -2 -5 -1 3
-1 7 6 -8 3 5 -4 -2
-2 4 9 8 3 1 -1 5
-9 10 -5 6 -2 -3 -2 1
5 2 -3 6 4 -4 -5 3
3 4 6 5 0 0 2 0
0 0 -3 1 4 0 -5 4
-8 -3 0 5 2 3 2 1
7 -9 3 0 -5 0 2 3
6 -8 10 3 -1 2 1 -2
-6 -6 -4 -9 -3 -4 -2 5
7 1 7 2 3 5 -3 0
9 5 2 9 2 5 1 1
5 10 10 -2 -1 -1 3 -1
2 10 -7 9 1 -4 -2 -4
-5 -7 4 0 4 -2 -3 -1
3 4 -5 6 0 5 -1 -3
-8 -5 2 -7 4 5 -2 -2
-6 2 -3 -5 5 -5 -2 -4
4 3 -3 -5 1 -1 1 -4
9 -3 -2 -6 4 -2 0 0
6 4 -2 8 2 -4 -3 0
-7 7 -2 -4 -5 -3 0 -4
9 -10 -8 -4 0 5 0 -2
8 2 -8 -9 2 2 5 -4
6 -8 7 7 2 5 3 -3
3 5 -9 5 -1 3 -5 3
-1 1 9 10 4 -2 5 4
-2 5 -7 0 2 2 -3 1
-6 -1 6 -2 4 5 -4 0
-9 -6 -3 7 3 0 -2 -5
3 1 1 -4 -1 5 3 -1
-8 0 -6 1 -5 0 4 2
-3 5 -2 8 -1 4 3 2
6 -5 4 -9 1 3 1 -3
3 0 -2 -2 5 4 4 0
5 0 4 -8 4 4 -4 4
-3 10 -10 -6 -3 -4 1 4
-1 8 -7 8 -5 3 -4 -5
4 -1 2 8 1 -5 -3 5
2 1 2 -7 -4 3 5 -5
-9 -6 -3 3 2 -5 1 5
3 -1 8 -5 -1 2 2 -5
1 -7 2 1 -3 1 -1 2
2 -6 -10 -1 -3 1 5 5
4 -4 1 -5 0 3 5 5
7 -4 -10 -6 -2 -4 -1 0
4 -7 -3 10 0 3 -5 -3
-4 4 -8 5 -4 -1 0 4
1 10 5 0 -5 5 0 -5
-2 -5 2 -3 -1 5 -2 5
9 10 -6 -3 0 4 4 -5
-1 6 -5 -6 -1 -3 -4 1
10 5 -2 -4 -4 -5 2 -5
7 -3 0 10 3 -3 2 -2
-1 4 -9 10 -2 0 0 -1
7 2 2 9 1 4 2 4
10 -5 -6 8 -2 2 3 3
-5 -1 -4 -9 5 5 1 -2
-3 7 -3 0 -3 -1 -1 1
-2 -3 7 -8 -5 -1 3 5
3 -7 0 -6 -5 1 0 1
-3 -9 9 -6 -3 1 -3 4
5 -9 4 4 4 1 -5 0
-10 -3 1 -6 5 -1 -2 4
2 -6 4 3 0 -5 -5 -5
8 4 -5 1 4 -5 2 1
1 -10 5 3 -2 3 3 5
-4 -9 0 -4 1 -2 -2 -2
0 -6 -8 -6 -2 4 -1 -5
5 -4 5 -8 -4 -5 1 1
5 9 -5 9 -4 1 2 -5
10 8 -2 0 3 -1 2 4
-7 -5 5 -8 4 -2 4 -3
6 9 -10 8 3 1 -2 -5
6 -2 -3 -9 2 3 -4 5
-1 -9 -6 6 -3 0 -1 4
6 -6 -6 6 4 3 4 -5
-3 -2 -4 6 -5 5 5 0
10 -5 -7 -3 4 -2 2 5
8 -8 -8 -9 -4 1 -4 -2
1 5 -5 6 -1 -5 4 4
-3 10 -8 6 -5 -4 5 4
3 1 -2 9 -5 4 5 1
3 9 -5 2 -4 4 1 -1
-9 0 7 -2 5 -2 -4 -5
-5 -6 -7 2 3 5 1 1
-1 7 5 -9 5 5 4 0
-4 9 1 7 -2 -3 0 5
-7 5 -8 -4 3 4 3 -2
-1 -2 -9 4 -2 -1 -4 2
7 5 -6 0 -3 2 -3 1
2 -5 -8 2 -1 4 1 2
-1 0 8 -5 5 5 5 -1
5 0 10 6 5 3 4 4
7 3 2 -9 -5 1 -5 -4
-4 -8 -9 10 5 3 2 4
3 -2 -4 -5 1 -4 -4 1
4 -7 -10 -5 -1 3 -5 4
8 -10 -1 2 -1 4 -3 -5
4 -2 9 -2 -1 3 2 3
2 -9 7 3 -5 3 2 -4
6 7 6 -6 1 -3 -1 -2
-3 -6 10 3 2 -1 5 -3
7 1 -6 8 5 5 -5 -2
-10 -5 -9 10 3 -3 -2 5
-5 9 7 0 -5 -2 1 -5
10 -9 -7 0 -4 -3 3 2
7 0 -5 -4 2 -2 1 0
-8 6 3 -1 -3 -4 1 5
6 -8 -4 5 0 5 -1 3
9 9 -8 10 -5 3 1 3
7 -3 4 4 -1 4 2 0
-1 7 10 -6 -5 5 3 -1
7 6 -4 -2 2 0 0 -5
-3 7 3 -5 3 -2 2 1
5 -3 2 -7 2 1 0 4
8 2 6 -5 2 1 4 -1
5 9 4 -1 -5 -5 -3 3
10 0 -5 -3 2 3 2 -1
2 -1 -5 6 2 1 -1 -4
-9 -2 -6 -9 -2 -1 -1 -5
-9 10 4 0 4 -2 2 0
-5 7 5 9 4 1 -4 0
0 -6 -2 -8 3 1 -4 5
4 8 -6 8 3 0 -3 -3
-3 3 10 -6 -2 1 5 -2
4 -8 -7 -1 3 4 -4 2
-10 0 2 -5 -1 -4 -1 3
-9 9 8 4 -2 -4 4 3
0 3 -7 5 5 5 -2 0
-10 4 5 -4 2 0 -1 2
8 -6 8 -7 -1 0 -5 3
-2 -3 -6 3 5 -5 5 -2
-9 -8 3 -3 3 -2 -1 -3
-10 2 1 -3 -5 5 5 3
5 -9 -4 -2 4 2 0 1
10 9 -9 1 5 -2 1 -3
-7 5 0 4 0 -2 -3 -5
0 5 6 3 3 -4 -5 5
9 -8 3 9 -1 -3 -1 0
6 4 7 -2 2 5 -5 -2
0 -4 -6 7 2 3 3 3
-10 7 -10 -8 0 3 -3 3
0 4 5 -1 1 2 4 2
8 -3 10 -4 -4 2 -5 3
-10 -2 8 10 2 -5 -4 0
1 5 -6 -7 -5 -5 -4 -5
-9 8 -10 3 1 -3 -3 -4
-2 -2 2 -9 1 -4 -1 -4
10 -8 -6 1 3 -5 -4 2
10 9 -7 0 -3 -1 -3 5
-4 -6 2 -9 3 5 2 1
2 8 -7 8 3 -1 -4 3
-2 -7 -6 6 5 2 1 -5
-9 9 6 6 4 -2 -1 -3
9 -10 -9 -4 1 -2 -5 -4
-9 -8 -6 -1 1 4 -1 2
-1 -2 -2 5 -1 -4 0 1
10 -8 10 7 0 -3 -5 -2
5 -7 5 8 4 -5 -2 5
0 8 10 -9 -1 0 -3 -4
-4 7 -8 -1 3 -5 1 5
-1 2 2 10 5 3 0 5
9 10 7 8 -4 -4 -2 -4
3 6 5 -1 3 -2 -4 0
-1 7 8 3 -1 -1 5 -2
-9 7 -1 2 -5 0 -2 -4
3 9 -10 2 -2 1 5 4
8 -10 8 -10 -3 1 -3 0
9 1 -3 -6 2 4 -1 4
1 1 -1 -4 -3 -3 0 -2
-10 -5 -8 -9 -2 4 -5 -5
2 1 -7 0 4 -2 1 1
8 7 -9 8 -1 -1 0 -1
-4 7 -7 -9 -5 3 -5 -5
-1 1 2 -1 -5 0 3 3
-9 -7 -2 -2 3 4 3 4
9 8 6 0 -2 4 5 -1
-9 0 3 4 -2 2 3 -4
-3 6 8 -5 3 -2 0 -5
-1 6 5 0 -2 5 4 -4
4 3 5 -1 5 0 -1 -3
-8 7 -6 -1 -2 2 1 -2
4 5 -4 6 0 -3 -5 -4
-6 -1 9 -9 -2 0 -5 5
-2 5 6 2 -3 -4 -4 0
1 0 -9 -5 3 -1 4 -2
-9 1 1 -2 1 1 -4 2
-6 9 -4 2 -3 -3 2 2
10 -2 6 7 3 5 -5 -4
-3 -9 -5 7 3 5 4 4
0 -9 -4 10 5 2 1 1
-4 2 -1 10 -4 -3 2 2
3 -8 6 -5 -5 -3 1 -5
7 -3 -7 1 -3 0 -2 -1
7 0 5 -10 2 -4 5 3
8 6 8 -7 3 -2 -4 -3
3 9 7 5 0 2 -5 1
0 2 -2 2 2 -4 2 1
-10 -4 3 -8 3 3 5 0
8 5 5 -7 5 -3 4 -3
-10 -10 1 -1 5 1 0 0
-1 -1 -4 8 -5 -3 -3 3
-2 9 -6 -3 2 -3 2 3
7 6 -9 -1 0 -2 1 -1
1 -9 -1 9 -4 2 -4 4
-10 -9 -10 10 1 4 1 3
-9 -3 8 3 -3 3 4 -4
7 -4 -8 2 0 4 -5 4
10 10 -9 1 2 -1 2 -2
-7 2 3 5 1 1 0 -3
8 7 4 -9 -5 -3 0 -5
-6 0 3 1 -4 4 4 -5
-8 1 3 -3 -4 0 1 -5
8 7 9 0 5 -5 1 -2
1 -6 -2 -10 1 -3 -2 1
-2 8 -1 -9 1 3 0 1
-6 1 -3 -10 -4 3 3 -2
-5 -6 -3 1 -3 -2 -3 5
-3 -7 1 2 -3 0 -2 -1
5 -2 0 -5 -4 2 -1 -1
4 9 7 -9 1 2 -5 1
-1 -9 9 3 5 -2 -5 3
-10 -2 -6 -7 -2 5 -4 3
5 1 -7 0 2 -3 2 -4
-1 0 8 -6 -1 0 5 3
9 1 6 -10 3 1 -3 2
-4 4 -3 3 1 -3 -5 3
10 -6 7 2 1 4 1 4
10 6 5 -4 3 0 5 0
5 1 -7 -10 4 0 -5 -5
-1 -3 4 10 5 -3 5 1
9 0 4 -2 1 4 -2 3
-9 2 -7 3 4 -1 0 -3
4 2 -5 -2 1 -4 5 -1
3 3 2 -3 1 -5 4 0
1 -3 4 -1 -3 -2 -2 -1
-6 -9 2 -8 5 4 -4 -1

Thanks in advance.

[zobayer]

PLEASE FOLLOW FORUM RULES, DO NOT OPEN NEW THREAD WHILE THERE IS ALREADY ONE OPENED. USE EXISTING THREADS.

Here are my output for your input,

Code: Select all

F
T
T
F
F
F
F
F
F
F
F
T
F
F
F
F
F
T
F
F
F
F
F
T
F
F
T
F
F
F
F
T
T
F
F
F
F
T
F
T
T
T
F
T
T
F
F
F
F
T
T
F
T
T
F
T
F
F
T
F
F
F
F
F
F
F
F
F
F
F
F
F
F
T
F
F
F
F
F
T
F
T
F
F
T
F
T
F
F
T
F
F
F
T
F
F
F
T
F
F
F
T
F
T
T
T
F
F
T
F
F
F
F
F
F
T
F
F
F
F
F
F
F
F
F
T
F
T
F
F
T
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
T
F
F
F
F
F
T
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
T
T
F
F
F
T
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
T
F
F
F
F
F
F
T
F
T
F
F
T
F
T
F
F
F
F
F
T
F
F
F
F
F
F
F
F
F
F
F
F
F
T
F
T
T
F
F
F
F
F
F
T
F
F
F
T
T
T
F
F
F
T
T
F
T
F
T
F
F
F
F
F
F
F
F
T
T
F
F
F
F
F
T
F
T
F
F
F
F
F
F
T
F
F
F
F
F
F
F
F
T
F
F
F
F
F
F
T
T
F
F
T
T
F
F
F
F
T
F
T
F
F
F
F
F
F
F
F
F
F
F
F
T
F
F
F
F
T
T
F
F
F
F
T
T
F
F
F
F
F
T
T
F
F
F
F
F
T
F
T
F
F
F
T
T
F
F
T
T
T
F
F
F
T
F
F
F
F
F
F
T
F
T
F
F
F
T
F
T
F
T
F
F
F
T
F
F
F
F
T
F
F
F
F
T
F
F
T
F
T
T
T
F
F
F
F
F
F
T
F
F
F
F
T
F
F
F
F
F
F
F
T
F
T
F
T
T
F
F
F
F
T
T
F
F
F
F
F
F
F
F
F
F
T
F
T
F
F
F
F
F
F
F
F
F
F
F
F
T
F
F
F
F
T
T
F
F
F
F
T
F
F
F
T
F
F
T
F
T
F
F
T
F
F
F
F
T
F
F

[S.H.Bouwhuis]

Thanks for testing Zobayer!

Edit:
Oh man, that's annoying. I have the same thing.
There apparently is some special case I haven't considered.

If someone knows a special case, please tell us.

Here is my source code in case someone is interested.

Code: Select all

//
// 191_Intersection: Determine whether a line intersects a rectangle
//

#include <cstdio>
#define _CRT_RAND_S
#include <cstdlib>
#include <ctime>

// The base types
#ifdef WIN32
  typedef __int8            int8;
  typedef __int16           int16;
  typedef __int32           int32;
  typedef __int64           int64;
  typedef unsigned __int8   uint8;
  typedef unsigned __int16  uint16;
  typedef unsigned __int32  uint32;
  typedef unsigned __int64  uint64;
#else
  typedef char                    int8;
  typedef short                   int16;
  typedef long                    int32;
  typedef long long int           int64;
  typedef unsigned char           uint8;
  typedef unsigned short          uint16;
  typedef unsigned long           uint32;
  typedef unsigned long long int  uint64;
#endif

// These macros safely delete (an array of) objects
#define SAFE_DELETE(pObj)       { if(pObj) { delete pObj;   pObj = NULL; } }
#define SAFE_DELETE_ARRAY(pArr) { if(pArr) { delete[] pArr; pArr = NULL; } }

// Approximation functions for doubles
#define EPSILON   1e-10
int8 Dbl_Compare(double dA, double dB) { return (dA + EPSILON < dB ? -1 : (dA - EPSILON > dB ? 1 : 0)); }
#define Dbl_IsSmaller(dA, dB)      (Dbl_Compare(dA, dB) == -1)
#define Dbl_IsSmallerEqual(dA, dB) (Dbl_Compare(dA, dB) !=  1)
#define Dbl_IsEqual(dA, dB)        (Dbl_Compare(dA, dB) ==  0)
#define Dbl_IsBiggerEqual(dA, dB)  (Dbl_Compare(dA, dB) != -1)
#define Dbl_IsBigger(dA, dB)       (Dbl_Compare(dA, dB) ==  1)

  // The line types
enum LineType { point, horizontal, slope, vertical };

// The definition of a vertex
struct VERTEX
{
  double dX;
  double dY;
};

// A line of the form y = ax + b
struct LINE
{
  VERTEX   vertA;       // The starting point of the line
  VERTEX   vertB;       // The ending point of the line
  LineType type;        // The type of the line (point, horizontal, slope, vertical)
  double   dSlope;      // The slope (is the 'a'  in y = ax + b)
  double   dIntersect;  // The y-intersect (is the 'b'  in y = ax + b)
};

// The definition of a rectangle
struct RECTANGLE
{
  LINE lineLeft;    // The left side of the rectangle
  LINE lineTop;     // The top side of the rectangle
  LINE lineRight;   // The right side of the rectangle
  LINE lineBottom;  // The bottom side of the rectangle
};

// Function prototypes
                   bool GetIntersect_Line_Line(const LINE *pLineA, const LINE *pLineB, VERTEX *pVertInter);
                   void GetLineEquation(LINE *pLine);
                   bool IsEqualVertex(const VERTEX *pVertA, const VERTEX *pVertB);
template <class T> T    Max(T tA, T tB) { return tA > tB ? tA : tB; }
template <class T> T    Min(T tA, T tB) { return tA < tB ? tA : tB; }
template <class T> void Swap(T *ptA, T *ptB);
                   bool VertexInRectangle(const VERTEX *pVert, const RECTANGLE *pRect);
                   bool VertexOnLine(const VERTEX *pVert, const LINE *pLine);

// Uncomment the next line to generate random input
//#define GENERATE_RANDOM_INPUT


//---------------------------------------------------------------------------------------------
//                                      F U N C T I O N S
//---------------------------------------------------------------------------------------------


// This function is the entrance of the app
int main()
{
  // Should we generate random inputs?
#ifdef GENERATE_RANDOM_INPUT

  // Show the amount of inputs we're generating
  printf("500\n");

  // Generate the inputs
  for(int32 i32Input=0;i32Input<500;i32Input++)
  {
    uint32 u32Rand;

    // Line coordinates : range x and y = [-10, 10]
    rand_s(&u32Rand);
    printf("%i ", int32(u32Rand % 21) - 10);
    rand_s(&u32Rand);
    printf("%i ", int32(u32Rand % 21) - 10);
    rand_s(&u32Rand);
    printf("%i ", int32(u32Rand % 21) - 10);
    rand_s(&u32Rand);
    printf("%i ", int32(u32Rand % 21) - 10);

    // Rectangle coordinates : range x and y = [-5, 5]
    rand_s(&u32Rand);
    printf("%i ", int32(u32Rand % 11) - 5);
    rand_s(&u32Rand);
    printf("%i ", int32(u32Rand % 11) - 5);
    rand_s(&u32Rand);
    printf("%i ", int32(u32Rand % 11) - 5);
    rand_s(&u32Rand);
    printf("%i\n", int32(u32Rand % 11) - 5);
  }

#else

  int32 i32TotInputs;

  // Get the amount of lines we need to process
  if(scanf("%i", &i32TotInputs) == 1)
  {
    // Get the next input
    while(i32TotInputs-- > 0)
    {
      int32 i32Left, i32Top, i32Right, i32Bottom;

      // Get the intersecting line
      if(scanf("%i %i %i %i", &i32Left, &i32Top, &i32Right, &i32Bottom) == 4)
      {
        LINE line;

        // Initialize the intersecting line
        line.vertA.dX = i32Left;
        line.vertA.dY = i32Top;
        line.vertB.dX = i32Right;
        line.vertB.dY = i32Bottom;
        GetLineEquation(&line);

        // Get the intersecting rectangle
        if(scanf("%i %i %i %i", &i32Left, &i32Top, &i32Right, &i32Bottom) == 4)
        {
          RECTANGLE rect;

          // Fix the coordinates
          if(i32Right < i32Left)
            Swap(&i32Left, &i32Right);
          if(i32Top < i32Bottom)
            Swap(&i32Top, &i32Bottom);

          // Initialize the intersecting rectangle (left side)
          rect.lineLeft.vertA.dX = i32Left;
          rect.lineLeft.vertA.dY = i32Top;
          rect.lineLeft.vertB.dX = i32Left;
          rect.lineLeft.vertB.dY = i32Bottom;
          GetLineEquation(&rect.lineLeft);

          // Initialize the intersecting rectangle (top side)
          rect.lineTop.vertA.dX = i32Left;
          rect.lineTop.vertA.dY = i32Top;
          rect.lineTop.vertB.dX = i32Right;
          rect.lineTop.vertB.dY = i32Top;
          GetLineEquation(&rect.lineTop);

          // Initialize the intersecting rectangle (right side)
          rect.lineRight.vertA.dX = i32Right;
          rect.lineRight.vertA.dY = i32Top;
          rect.lineRight.vertB.dX = i32Right;
          rect.lineRight.vertB.dY = i32Bottom;
          GetLineEquation(&rect.lineRight);

          rect.lineBottom.vertA.dX = i32Left;
          rect.lineBottom.vertA.dY = i32Bottom;
          rect.lineBottom.vertB.dX = i32Right;
          rect.lineBottom.vertB.dY = i32Bottom;
          GetLineEquation(&rect.lineBottom);

          // Check whether either (or both) of the end points of the line resides on/within the rectangle
          if(VertexInRectangle(&line.vertA, &rect) || VertexInRectangle(&line.vertB, &rect))
            printf("T\n");
          else
          {
            VERTEX vertIntersect;

            // Both end points of the line are outside of the rectangle

            // Check whether the line intersects any of the rectangle's sides
            if(GetIntersect_Line_Line(&line, &rect.lineLeft,   &vertIntersect) ||
               GetIntersect_Line_Line(&line, &rect.lineTop,    &vertIntersect) ||
               GetIntersect_Line_Line(&line, &rect.lineRight,  &vertIntersect) ||
               GetIntersect_Line_Line(&line, &rect.lineBottom, &vertIntersect))
              printf("T\n");
            else
              printf("F\n");
          }
        }
      }
    }
  }

#endif

  return 0;
}


//---------------------------------------------------------------------------------------------


// This function determines whether 2 lines intersect (and where)
bool GetIntersect_Line_Line(const LINE *pLineA, const LINE *pLineB, VERTEX *pVertInter)
{
  bool bIntersecting = false;

  // Do we have parallel lines?
  if(pLineA->type == pLineB->type && Dbl_IsEqual(pLineA->dSlope, pLineB->dSlope))
  {
    // Are they overlapping or touching?
    if(VertexOnLine(&pLineA->vertA, pLineB) || VertexOnLine(&pLineA->vertB, pLineB)  ||  VertexOnLine(&pLineB->vertA, pLineA) || VertexOnLine(&pLineB->vertB, pLineA))
      bIntersecting = true;
  }
  else
  {
    // Do we have 1 vertical line?
    if(pLineA->type == vertical || pLineB->type == vertical)
    {
      const LINE *pLineSloped, *pLineVert;

      // Determine which line is vertical and which is sloped
      if(pLineA->type == vertical) { pLineSloped = pLineB; pLineVert = pLineA; }
      else                         { pLineSloped = pLineA; pLineVert = pLineB; }

      // Line sloped: y = ax + b, Line vertical: x = c

      // The intersection point is: (x,y) = (c, ac+b)
      pVertInter->dX = pLineVert->vertA.dX;
      pVertInter->dY = pLineSloped->dSlope * pLineVert->vertA.dX + pLineSloped->dIntersect;

      // Does the intersection point lie on line Sloped and on line Vertical?
      if(((Dbl_IsSmallerEqual(pLineSloped->vertA.dX, pVertInter->dX) && Dbl_IsBiggerEqual(pLineSloped->vertB.dX,  pVertInter->dX)) ||
          (Dbl_IsBiggerEqual(pLineSloped->vertA.dX,  pVertInter->dX) && Dbl_IsSmallerEqual(pLineSloped->vertB.dX, pVertInter->dX)))
        &&
         ((Dbl_IsSmallerEqual(pLineVert->vertA.dY, pVertInter->dY) && Dbl_IsBiggerEqual(pLineVert->vertB.dY,  pVertInter->dY)) ||
          (Dbl_IsBiggerEqual(pLineVert->vertA.dY,  pVertInter->dY) && Dbl_IsSmallerEqual(pLineVert->vertB.dY, pVertInter->dY))))
      {
        // The lines intersect
        bIntersecting = true;
      }
    }
    else
    {
      // Line A: y = ax + b, Line B: y = cx + d
      // ax+b = cx+d  =>  x = (d-b)/(a-c)

      // Are the lines not parallel?
      if(!Dbl_IsEqual(pLineA->dSlope, pLineB->dSlope))
      {
        // The intersection point is: (x,y) = ((d-b)/(a-c), a(d-b)/(a-c) + b)
        pVertInter->dX = (pLineB->dIntersect - pLineA->dIntersect) /
          (pLineA->dSlope - pLineB->dSlope);
        pVertInter->dY = ((pLineA->dSlope * (pLineB->dIntersect - pLineA->dIntersect) /
          (pLineA->dSlope - pLineB->dSlope))) +
          pLineA->dIntersect;

        // Does the intersecting point lie on line A and on line B?
        if(((Dbl_IsSmallerEqual(pLineA->vertA.dX, pVertInter->dX) && Dbl_IsBiggerEqual(pLineA->vertB.dX,  pVertInter->dX)) ||
            (Dbl_IsBiggerEqual(pLineA->vertA.dX,  pVertInter->dX) && Dbl_IsSmallerEqual(pLineA->vertB.dX, pVertInter->dX)))
          &&
           ((Dbl_IsSmallerEqual(pLineB->vertA.dX, pVertInter->dX) && Dbl_IsBiggerEqual(pLineB->vertB.dX,  pVertInter->dX)) ||
            (Dbl_IsBiggerEqual(pLineB->vertA.dX,  pVertInter->dX) && Dbl_IsSmallerEqual(pLineB->vertB.dX, pVertInter->dX))))
        {
          // The lines intersect
          bIntersecting = true;
        }
      }
    }
  }

  return bIntersecting;
}


//---------------------------------------------------------------------------------------------


// This function constructs the equation of the line going through the 2 vertices
void GetLineEquation(LINE *pLine)
{
  // y = ax + b
  // a = slope, b = y-intercept, VertA = (x1,y1), VertB = (x2,y2)
  //
  //     y2-y1     x2*y1-x1*y2
  // y = ----- x + -----------
  //     x2-x1        x2-x1

  // Do we have a horizontal line?
  if(Dbl_IsEqual(pLine->vertB.dY, pLine->vertA.dY))
  {
    // Do we have a line with 2 identical vertices?
    if(Dbl_IsEqual(pLine->vertB.dX, pLine->vertA.dX))
    {
      // We have a line consisting of exactly 1 point
      pLine->type       = point;
      pLine->dSlope     = 0.0;
      pLine->dIntersect = 0.0;
    }
    else
    {
      // We have an equation of the form y = b
      pLine->type       = horizontal;
      pLine->dSlope     = 0.0;
      pLine->dIntersect = pLine->vertA.dY;
    }
  }
  // Do we have a vertical line?
  else if(Dbl_IsEqual(pLine->vertB.dX, pLine->vertA.dX))
  {
    // We have an equation of the form x = c
    pLine->type       = vertical;
    pLine->dSlope     = 0.0;
    pLine->dIntersect = pLine->vertA.dX;
  }
  else
  {
    // We have an equation of the form y = ax + b
    pLine->type       = slope;
    pLine->dSlope     = (pLine->vertB.dY - pLine->vertA.dY) / (pLine->vertB.dX - pLine->vertA.dX);
    pLine->dIntersect = (pLine->vertB.dX * pLine->vertA.dY - pLine->vertA.dX * pLine->vertB.dY) / (pLine->vertB.dX - pLine->vertA.dX);
  }

#ifdef TEST
  PrintLineEquation(pLine);
#endif
}


//---------------------------------------------------------------------------------------------


// This function checks whether the 2 vertices are equal
bool IsEqualVertex(const VERTEX *pVertA, const VERTEX *pVertB)
{
  return Dbl_IsEqual(pVertA->dX, pVertB->dX) &&
         Dbl_IsEqual(pVertA->dY, pVertB->dY);
}


//---------------------------------------------------------------------------------------------


// This function swaps 2 elements around
template <class T> void Swap(T *ptA, T *ptB)
{
  T tTemp;

  // Swap the elements around
  tTemp = *ptA;
  *ptA  = *ptB;
  *ptB  = tTemp;
}


//---------------------------------------------------------------------------------------------


// This function determines whether the vertex lies on or within the rectangle
bool VertexInRectangle(const VERTEX *pVert, const RECTANGLE *pRect)
{
  return Dbl_IsBiggerEqual(pVert->dX, pRect->lineLeft.vertA.dX)    &&  Dbl_IsSmallerEqual(pVert->dX, pRect->lineRight.vertA.dX) &&
         Dbl_IsBiggerEqual(pVert->dY, pRect->lineBottom.vertA.dY)  &&  Dbl_IsSmallerEqual(pVert->dY, pRect->lineTop.vertA.dY);
}


//---------------------------------------------------------------------------------------------


// This function determines whether the vertex lies on the line
bool VertexOnLine(const VERTEX *pVert, const LINE *pLine)
{
  bool bVertexOnLine = false;

  // What type of line do we have?
  if(pLine->type == vertical)
  {
    // x = c

    // Does the vertex lie on the line?
    if(Dbl_IsEqual(pVert->dX, pLine->vertA.dX))
    {
      // Does the vertex lie on the line section?
      if(pVert->dY >= Min(pLine->vertA.dY, pLine->vertB.dY)  &&  pVert->dY <= Max(pLine->vertA.dY, pLine->vertB.dY))
        bVertexOnLine = true;
    }
  }
  else if(pLine->type == horizontal)
  {
    // y = b

    // Does the vertex lie on the line?
    if(Dbl_IsEqual(pVert->dY, pLine->vertA.dY))
    {
      // Does the vertex lie on the line section?
      if(pVert->dX >= Min(pLine->vertA.dX, pLine->vertB.dX)  &&  pVert->dX <= Max(pLine->vertA.dX, pLine->vertB.dX))
        bVertexOnLine = true;
    }
  }
  else if(pLine->type == point)
  {
    // Does the vertex lie on the line?
    if(IsEqualVertex(pVert, &pLine->vertA))
      bVertexOnLine = true;
  }
  else if(pLine->type == slope)
  {
    // Does the vertex lie on the line?
    if(Dbl_IsEqual(pVert->dY, pLine->dSlope * pVert->dX + pLine->dIntersect))
    {
      // Does the vertex lie on the line section?
      if(pVert->dX >= Min(pLine->vertA.dX, pLine->vertB.dX)  &&  pVert->dX <= Max(pLine->vertA.dX, pLine->vertB.dX))
        bVertexOnLine = true;
    }
  }

  return bVertexOnLine;
}

[Scarecrow]

can anyone find out what's wrong with my code? i can't find where's the fault. seems the logic is ok

Code: Select all

#include<stdio.h>
#define check_position(a,b) (a>=x1 && a<=x2 && (x3<=x4?(a>=x3 && a<=x4):(a>=x4 && a<=x3)) && b<=y1 && b>=y2 && (y3>=y4?(b<=y3 && b>=y4):(b<=y4 && b>=y3)))

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int test,a,b,c,x1,y1,x2,y2,x3,y3,x4,y4;double a1,a2,b1,b2,a3,a4,b3,b4;
    for(scanf("%d",&test);test;test--)
    {
        scanf("%d %d %d %d %d %d %d %d",&x3,&y3,&x4,&y4,&x1,&y1,&x2,&y2);
        a=y3-y4;
        b=x4-x3;
        c=x3*a+y3*b;
        if(!a)
            check_position(x1,y3) || check_position(x2,y3)?printf("T\n"):printf("F\n");
        else if(!b)
            check_position(x3,y1) || check_position(x3,y2)?printf("T\n"):printf("F\n");
        else
        {
            a1=x1; b1=(double)(c-a*x1)/b;
            a2=x2; b2=(double)(c-a*x2)/b;
            a3=(double)(c-b*y1)/a; b3=y1;
            a4=(double)(c-b*y2)/a; b4=y2;
            check_position(a1,b1) || check_position(a2,b2) || check_position(a3,b3) || check_position(a4,b4)?printf("T\n"):printf("F\n");
        }
    }
    return 0;
}