378 - Intersecting Lines

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Mahbub
New poster
Posts: 26
Joined: Thu Aug 08, 2002 8:04 am

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

Code: Select all


#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
New poster
Posts: 15
Joined: Mon Oct 14, 2002 3:45 pm
Contact:

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
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

378 Why Wrong Answer?

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]
"Learning without thought is useless;thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

dpitts
New poster
Posts: 31
Joined: Tue Jun 17, 2003 10:10 pm

I'm also getting WA

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
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

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.
"Learning without thought is useless;thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

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
New poster
Posts: 28
Joined: Tue Nov 04, 2003 6:45 am
Location: Bangladesh

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... :lol:

kathmolla
New poster
Posts: 6
Joined: Tue Nov 30, 2004 2:27 am

fade up with WA(378)

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 .
hey why doing this

Lord Nemrod
New poster
Posts: 12
Joined: Mon Mar 28, 2005 7:55 pm
Contact:

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
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

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
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

378 - Intersecting Lines

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
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

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
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

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

Somebody post their output please.

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

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
Where's the "Any" key?

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

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

Thanks Solaris.
I also get the same. :-? So where can be the trick?

Post Reply

Return to “Volume 3 (300-399)”