378 - Intersecting Lines

Mahbub · Post by **Mahbub** » Thu Nov 28, 2002 3:10 pm


#include <stdio.h>

double det (double a11, double a12, double a21, double a22)
{
	return a11 * a22 - a12 * a21;
}

double main()
{
	int N;
	double d,area,x1,x2,y1,y2,x3,y3,x4,y4;
	double x,y;

	scanf ( "%d", &N );

	printf ( "INTERSECTING LINES OUTPUT\n" );

	while ( N-- )
	{
		scanf ( "%lf %lf %lf %lf", &x1, &y1, &x2, &y2) ;	
		scanf ( "%lf %lf %lf %lf", &x3, &y3, &x4, &y4) ;	

		d = det ( x1 - x2, y1 - y2, x3 - x4, y3 - y4 ) ;

		if ( d == 0 )
		{
			area = x1 * y2 + x2 * y3 + x3 * y1 -
				   y1 * x2 - y2 * x3 - y3 * x1 ;

			if ( area == 0 )
			{
				printf ( "LINE\n" );	
			}
			else
			{
				printf ( "NONE\n" ) ;	
			}
		}
		else
		{
			x = det ( det ( x1, y1, x2, y2 ), x1 - x2,
		              det ( x3, y3, x4, y4 ), x3 - x4 ) / d ;

			y = det ( det ( x1, y1, x2, y2 ), y1 - y2,
		              det ( x3, y3, x4, y4 ), y3 - y4 ) / d ;

			printf ("POINT %.2lf %.2lf\n",x,y );
		}

	}
	
	printf ( "END OF OUTPUT\n" );

	return 0;
}

cym · Post by **cym** » Sat Jan 04, 2003 2:44 am

any tricky test cases???
the following is my code:

[cpp]

#include<stdio.h>
void main(void)
{
double x1,x2,x3,x4,y1,y2,y3,y4,a1,b1,a2,b2;
double px,py;
int i,n,check;

while(scanf("%d",&n)!=-1 && n>0)
{
printf("INTERSECTING LINES OUTPUT\n");
for(i=1;i<=n;i++)
{
scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);
check=0;
if(x1==x2)
if(x3==x4)
check=1;
else
{
check=2;
a2=(y4-y3)/(x4-x3);
b2=y3-a2*x3;
}
else
{
a1=(y2-y1)/(x2-x1);
b1=y1-a1*x1;
if(x3==x4)
check=3;
else
{
a2=(y4-y3)/(x4-x3);
b2=y3-a2*x3;
}
}
switch (check){
case 0 :
if(a1==a2)
if(b1==b2)
printf("LINE\n");
else
printf("NONE\n");
else
{
px=(b2-b1)/(a1-a2);
py=a1*px+b1;
printf("POINT %.2lf %.2lf\n",px,py);
}
break;
case 1 :
if(x1==x3)
printf("LINE\n");
else
printf("NONE\n");
break;
case 2 :
px=x1;
py=a2*px+b2;
printf("POINT %.2lf %.2lf\n",px,py);
break;
case 3 :
px=x3;
py=a1*x3+b1;
printf("POINT %.2lf %.2lf\n",px,py);
break;
}
}
printf("END OF OUTPUT\n");
}
}

[/cpp][/cpp]

Morning · Post by **Morning** » Wed Mar 17, 2004 4:08 pm

[cpp]
#include <iostream>
using namespace std;
double absDouble(double number)
{
if(number < 0) return (-1.0 * number);
else return number;
}
int main(int argc, char *argv[])
{
int numOfCase;
double x1,y1,x2,y2,x3,y3,x4,y4,k1,k2,b1,b2,interX,interY;
cout<<"INTERSECTING LINES OUTPUT"<<endl;
cin>>numOfCase;
while(numOfCase > 0)
{
numOfCase--;
cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;
if (x2 - x1 != 0 && x4 - x3 != 0)
{
k1 = (y2 - y1) / (x2 - x1);
k2 = (y4 - y3) / (x4 - x3);
b1 = y1 - k1 * x1;
b2 = y3 - k2 * x3;

if (absDouble(k1 - k2) < 0.00001)
{
if (absDouble(b1 - b2) < 0.00001)
{
cout<<"LINE"<<endl;
}
else
{
cout<<"NONE"<<endl;
}
}
else
{
interX = (b2 - b1) / (k1 - k2);
interY = k1 * interX + b1;
cout.setf(ios::fixed);
cout.setf(ios::showpoint);
cout.precision(2);
cout<<"POINT "<<interX<<" "<<interY<<endl;
}
}
else
{
if (x2 - x1 == 0 && x4 - x3 == 0)
{
cout<<"NONE"<<endl;//couz The point(x1,y1) is always distinct from(x2,y2). Likewise with (x3,y3) and (x4,y4) .
}
else
{
if (x2 - x1 == 0)
{
k2 = (y4 - y3) / (x4 - x3);
b2 = y3 - k2 * x3;
interX = x1;
interY = k2 * interX + b2;
cout.setf(ios::fixed);
cout.setf(ios::showpoint);
cout.precision(2);
cout<<"POINT "<<interX<<" "<<interY<<endl;
}
else
{
k1 = (y2 - y1) / (x2 - x1);
b1 = y1 - k1 * x1;
interX = x3;
interY = k1 * interX + b1;
cout.setf(ios::fixed);
cout.setf(ios::showpoint);
cout.precision(2);
cout<<"POINT "<<interX<<" "<<interY<<endl;
}
}
}
}
cout<<"END OF OUTPUT"<<endl;
return 0;
}[/cpp]

dpitts · Post by **dpitts** » Wed Mar 24, 2004 2:17 am

I'm also getting WA,

Whats your output for this:

Code: Select all

8
0 0 1 1 0 1 1 0
0 1 2 1 0 0 2 0
0 1 2 1 1 2 1 3
1 0 1 2 1 1 1 0
0 0 2 0 0 1 2 1
1 2 1 3 0 1 2 1
1 1 1 0 1 0 1 2
-2 -2 2 2 1 -1 -1 1

My WA output (that seems to be okay when checked manually) is

Code: Select all

INTERSECTING LINES OUTPUT
POINT 0.50 0.50
NONE
POINT 1.00 1.00
LINE
NONE
POINT 1.00 1.00
LINE
POINT 0.00 0.00
END OF OUTPUT

Any other test cases?

Morning · Post by **Morning** » Wed Mar 24, 2004 7:52 am

ur output helps me to find my mistakes,thanks.
I just change the
[cpp]
if (x2 - x1 == 0 && x4 - x3 == 0)
{
cout<<"NONE"<<endl;//couz The point(x1,y1) is always distinct from(x2,y2). Likewise with (x3,y3) and (x4,y4) .
}
[/cpp]
to
[cpp]
if (x2 - x1 == 0 && x4 - x3 == 0)
{
if(x2 == x4) cout<<"LINE"<<endl;
else cout<<"NONE"<<endl }
[/cpp]
and got AC:)
ur output is ok,but there might be some other mistakes in ur code.
Hope u can get AC soon.

WR · Post by WR » Wed Mar 24, 2004 2:51 pm

To dpitts:

my AC program returns

POINT 0.00 -0.00

for the last case!

Maybe that can help.

Rajib · Post by **Rajib** » Wed Jul 07, 2004 9:50 am

But my AC code give the output for the last case...

POINT 0.00 0.00

I think there is no input like this...

kathmolla · Post by **kathmolla** » Wed Dec 15, 2004 6:11 pm

i dont know why my prog gets WA . all the inputs of this forum works perfectly . can anyone find some stupid inputs and help me . i am really
fade up with this problem .

Lord Nemrod · Post by **Lord Nemrod** » Wed Apr 06, 2005 1:41 pm

Try considering lines that are vertical i.e x=a. You can't make this line as y = kx+b

roticv · Post by **roticv** » Sat Aug 06, 2005 7:09 pm

Try the following input. I think it is helpful for anyone here, because it showed me all the bugs I had (I had tonnes of WA for this qn and I am happy to solve this qn as it is one of my rare comp geom qn).

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

mamun · Post by **mamun** » Fri Oct 28, 2005 9:22 pm

I passed the samples I/O given in the threads. Still getting WA. Can anybody send many more? Thanks in advance.

mamun · Post by **mamun** » Fri Dec 09, 2005 6:37 pm

Nothing? Well, I give here some random input. Can sombody post his accepted output.

Code: Select all

30
106 860 288 -920 573 158 -58 -730
660 151 349 998 302 577 715 551
478 975 439 720 -483 -747 120 -209
-836 839 -889 596 -803 -49 -249 447
-552 -963 538 68 -929 512 23 -875
861 157 611 385 382 693 189 846
286 690 591 476 408 -547 188 -337
520 -173 99 -828 -862 304 -35 -813
293 -428 -762 359 -72 -347 -192 113
-255 -363 -95 -294 -724 83 443 318
842 852 -372 39 729 -818 770 627
162 606 -499 -58 -104 636 227 -236
-859 49 896 -744 844 270 813 -209
996 190 364 -300 -796 978 353 -353
-925 -506 967 -609 537 -419 367 94
166 808 -901 -110 -248 527 -947 355
278 -121 374 674 587 388 -634 -426
739 -559 477 480 -565 110 290 -840
-814 196 62 887 -425 706 -975 252
436 948 615 -312 509 960 -819 309
81 440 133 -101 142 309 903 528
638 888 -995 -410 498 -714 128 170
287 968 843 75 -483 537 -92 114
-377 696 452 -489 605 417 966 -736
296 301 -607 -475 851 140 369 778
347 98 978 166 561 520 240 229
625 366 -995 -873 304 270 -717 194
893 223 -722 -967 752 880 11 775
452 498 733 -748 556 489 278 941
-20 609 -988 324 -221 -761 498 -406

(They are really random. Seems all are intersecting)

mamun · Post by **mamun** » Mon Jan 02, 2006 6:45 pm

Somebody post their output please.

Solaris · Post by **Solaris** » Tue Jan 03, 2006 8:04 am

My AC code gives the following o/p ... hope this helps

INTERSECTING LINES OUTPUT
POINT 227.49 -328.23
POINT 508.35 564.01
POINT 324.87 -26.21
POINT -1084.68 -301.19
POINT -166.73 -598.58
POINT -449.44 1352.12
POINT -4144.68 3798.74
POINT 41.89 -916.85
POINT -133.96 -109.50
POINT 2095.99 650.86
POINT 775.11 807.21
POINT -22.33 420.84
POINT 781.72 -692.36
POINT 330.00 -326.36
POINT 593.22 -588.65
POINT -125.60 557.12
POINT 317.79 208.53
POINT 1012.21 -1642.46
POINT -5969.27 -3870.54
POINT 439.16 925.76
POINT 94.89 295.44
POINT 29.82 404.58
POINT 2697.99 -2904.33
POINT 1242.42 -1618.85
POINT 558.77 526.81
POINT 61.56 67.24
POINT 520.56 286.12
POINT 2030.51 1061.17
POINT 394.99 750.78
POINT 6355.47 2486.08
END OF OUTPUT

mamun · Post by **mamun** » Tue Jan 03, 2006 3:02 pm

Thanks Solaris.
I also get the same.

So where can be the trick?

OJ Board

378 - Intersecting Lines

378 Why Wrong Answer?

I'm also getting WA

fade up with WA(378)

378 - Intersecting Lines