378 - Intersecting Lines

Moderator: Board moderators

Oronno
New poster
Posts: 21
Joined: Sun Jul 09, 2006 1:42 pm
Location: Dhaka
Contact:

Thanks everyone

Thanks everyone for helping. Now i get AC.
Actually, "eps" has no affect on this problem. But i think, its a good programming habit to use it.

The only problem in my code was that, i thought that, for checking the formula-
a1/a2 = b1/b2 = c1/c2
it is enough to check-

Code: Select all

``a1/a2==b1/b2 && b1/b2==c1/c2 ``
BUT its not right for all time. So i need to check that-

Code: Select all

`` a1/a2==b1/b2 && b1/b2==c1/c2 && a1/a2==c1/c2``
Hope it will help for the users who are still getting WA!!
I like programming but i am so lazy to do it...

AcmNightivy
New poster
Posts: 36
Joined: Tue Dec 04, 2007 10:20 am
it is enough to check- Code:
a1/a2==b1/b2 && b1/b2==c1/c2

BUT its not right for all time. So i need to check that-Code:
a1/a2==b1/b2 && b1/b2==c1/c2 && a1/a2==c1/c2

Why?Thx``

Oronno
New poster
Posts: 21
Joined: Sun Jul 09, 2006 1:42 pm
Location: Dhaka
Contact:
AcmNightivy wrote:
it is enough to check- Code:
a1/a2==b1/b2 && b1/b2==c1/c2

BUT its not right for all time. So i need to check that-Code:
a1/a2==b1/b2 && b1/b2==c1/c2 && a1/a2==c1/c2

Why?Thx``
well, check your code putting a1/a2==b1/b2 && b1/b2==c1/c2 formula for this input-

Code: Select all

``````1
1 0 1 1 2 0 2 1 ``````
Correct Result will be: NONE
Now try to find out why....
I like programming but i am so lazy to do it...

AcmNightivy
New poster
Posts: 36
Joined: Tue Dec 04, 2007 10:20 am
I inderstand yours.But there still somtthing wrong in my code.
I just tested your and my code also get NONE.
I have tested lot of cases and all of them get the right ansewers..
help~

Code: Select all

``Remove after got AC.``
Last edited by AcmNightivy on Sat Feb 09, 2008 9:49 am, edited 1 time in total.

Oronno
New poster
Posts: 21
Joined: Sun Jul 09, 2006 1:42 pm
Location: Dhaka
Contact:
Test this input:

Code: Select all

``````5
12 12 12 12 45 45 45 45
45 12 45 12 45 12 45 12
1 2 3 6 4 7 8 9
12 45 89 78 12 45 89 78
1 1 2 2 3 3 6 6
``````
Correct output should be:

Code: Select all

``````INTERSECTING LINES OUTPUT
LINE
LINE
POINT 3.33 6.67
LINE
LINE
END OF OUTPUT
``````
But you program gives the output:

Code: Select all

``````INTERSECTING LINES OUTPUT
NONE
LINE
LINE
LINE
END OF OUTPUT
POINT 3.33 6.67
``````
Hope it will help...
I like programming but i am so lazy to do it...

AcmNightivy
New poster
Posts: 36
Joined: Tue Dec 04, 2007 10:20 am
The point (x1,y1) is always distinct from(x2,y2). Likewise with and (x3,y3) from (x4,y4).
But the case:
12 12 12 12 45 45 45 45
is not a right input..
INTERSECTING LINES OUTPUT
NONE
LINE
POINT 3.33 6.67
LINE
LINE
END OF OUTPUT
Press any key to continue
So there's nothing wrong with my code i think..

AcmNightivy
New poster
Posts: 36
Joined: Tue Dec 04, 2007 10:20 am
Oronno wrote:Test this input:

Code: Select all

``````5
12 12 12 12 45 45 45 45
Correct output should be:
[code]
LINE
But you program gives the output:
NONE
[/quote]
my roommates' AC code also give the result of NONE..``````

AcmNightivy
New poster
Posts: 36
Joined: Tue Dec 04, 2007 10:20 am
help..

AcmNightivy
New poster
Posts: 36
Joined: Tue Dec 04, 2007 10:20 am
it has puzzled me for 2 weeks...help!

AcmNightivy
New poster
Posts: 36
Joined: Tue Dec 04, 2007 10:20 am
really i can't find the mistake...
three weeks...

Mata
New poster
Posts: 18
Joined: Mon Dec 17, 2007 11:35 pm
Location: Queretaro
Contact:

Wa

Hi, I try the cases in the forum and it is correct but i still reciving wa, what is wrong with this code?

Code: Select all

``````#include <iostream>
int main()
{
int n=0;
scanf("%d\n",&n);
printf("INTERSECTING LINES OUTPUT\n");
while(n>0)
{
n--;
double x1=0.0,y1=0.0,x2=0.0,y2=0.0,kx1=0.0,ky1=0.0,kx2=0.0,ky2=0.0;
scanf("%lf %lf %lf %lf %lf %lf %lf %lf\n",&x1,&y1,&x2,&y2,&kx1,&ky1,&kx2,&ky2);
if(x1==x2)/**/
{
if(kx1==kx2)/**/
{
if(kx1==x1)/*LINE*/
printf("LINE\n");
else/*NONE*/
printf("NONE\n");
}
else if(ky1==ky2)/*POINT*/
{
double px=0.0,py=0.0;
px=x1;
py=ky1;
printf("POINT %.2lf %.2lf\n",px,py);
}
else/*POINT*/
{
double px=0.0,py=0.0, m2=(ky2-ky1)/(kx2-kx1);
px=x1;
py=m2*(px-kx1)+ky1;
printf("POINT %.2lf %.2lf\n",px,py);
}
}
else if(y1==y2)/**/
{
if(kx1==kx2)/*POINT*/
{
double px=0.0,py=0.0;
px=kx1;
py=y1;
printf("POINT %.2lf %.2lf\n",px,py);
}
else if(ky1==ky2)
{
if(ky1==y1)/*LINE*/
printf("LINE\n");
else/*NONE*/
printf("NONE\n");
}
else/*POINT*/
{
double px=0.0,py=0.0,m2=(ky2-ky1)/(kx2-kx1);
py=y1;
px=((py-ky1)/m2)+kx1;
printf("POINT %.2lf %.2lf\n",px,py);
}
}
else
{
if(kx1==kx2)/*POINT*/
{
double px=0.0,py=0.0, m1=(y2-y1)/(x2-x1);
px=kx1;
py=m1*(px-x1)+y1;
printf("POINT %.2lf %.2lf\n",px,py);
}
else if(ky1==ky2)/*POINT*/
{
double px=0.0,py=0.0,m1=(y2-y1)/(x2-x1);
py=ky1;
px=((py-y1)/m1)+x1;
printf("POINT %.2lf %.2lf\n",px,py);
}
else/**/
{
double m1=(y2-y1)/(x2-x1),m2=(ky2-ky1)/(kx2-kx1),testx1=5.0,testx2=1.0,testy1=0.0,testy2=0.0, testky1=0.0,testky2=0.0;
testy1=m1*(testx1-x1)+y1;
testy2=m1*(testx2-x1)+y1;
testky1=m2*(testx1-kx1)+ky1;
testky2=m2*(testx2-kx1)+ky1;
if(m1==m2&&testy1==testky1&&testy2==testky2)/*LINE*/
printf("LINE\n");
else if(m1==m2)/*NONE*/
printf("NONE\n");
else/*POINT*/
{
double px=0.0,py=0.0;
px=(x1*(y2*(kx1-kx2)-kx1*ky2+ky1*kx2)-x2*(y1*(kx1-kx2)-kx1*ky2+ky1*kx2))/(x1*(ky1-ky2)+y1*(kx2-kx1)+x2*(ky2-ky1)+y2*(kx1-kx2));
py=m1*(px-x1)+y1;
printf("POINT %.2lf %.2lf\n",px,py);
}
}
}
}
printf("END OF OUTPUT");
return 0;
}
``````
/********************************
********************************/

linux
Learning poster
Posts: 56
Joined: Sat Jul 01, 2006 12:21 pm
Location: CA-95054
Contact:

378

oronno wrote

Code: Select all

``````BUT its not right for all time. So i need to check that-Code:
a1/a2==b1/b2 && b1/b2==c1/c2 && a1/a2==c1/c2
``````
if a1/a2 = b1/b2 & b1/b2 =c1/c2 then there's no to doubt on a1/a2 =c1/c2
so the single check gives AC.
Last edited by linux on Thu Sep 11, 2008 9:30 pm, edited 1 time in total.
Solving for fun..

linux
Learning poster
Posts: 56
Joined: Sat Jul 01, 2006 12:21 pm
Location: CA-95054
Contact:

378

AcmNightivy wrote:

Code: Select all

``````         else   //k1,k2 all exist,find point
{
if(k1 == k2)
{
if(b1 == b2)   //line
results.flag = 2;
else         //parallel
results.flag = 0;
}
else
{
results.flag = 1;
results.x = (float)(b2 - b1)/(k1 - k2);
results.y = k1 * results.x + b1;
}
}
``````
You can not check equality for floating numbers like this. Do it using EPS. For example

Code: Select all

`````` if ((fabs(a - b)) < eps) {
CODE_HERE // eps is a least floating value
}
``````
Solving for fun..

AcmNightivy
New poster
Posts: 36
Joined: Tue Dec 04, 2007 10:20 am
Thanks~linux
Let me try~Maybe it is the problem exist~Thanks~

Rafa3p
New poster
Posts: 5
Joined: Sun Dec 25, 2011 1:32 am

Problem 378

I don't know why I'm getting WA.
For this test case I'm getting the same answer from uva.toolkit

Code: Select all

``````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``````
My code :

Code: Select all

``````#include <stdio.h>
int main(void)
{
int n,x1,x2,y1,y2;
double a1,a2,b1,b2,c1,c2,X,Y; /*Line Eq: ax+by+c=*/
printf("INTERSECTING LINES OUTPUT\n");
scanf("%d",&n);
while(n--)
{
scanf(" %d %d %d %d ",&x1,&y1,&x2,&y2);
if(x1^x2){ /*finding first line eq*/
b1=1.0;
a1 = (double) (y1-y2)/(x2-x1);
c1 = (double) -(a1*x1+y1);
}else{/*x1==x2 -> vertical line*/
a1=1.0; b1=0.0; c1 = -x1;
}

scanf(" %d %d %d %d ",&x1,&y1,&x2,&y2);
if(x1^x2){ /*finding second line eq*/
b2=1.0;
a2 = (double) (y1-y2)/(x2-x1);
c2 = (double) -(a2*x2+y2);
}else{/*x1==x2 -> vertical line*/
a2=1.0; b2=0.0; c2 = -x1;
}

if((a1==a2) &&(b1==b2)){ /*True ->parallel*/
if(c1==c2)printf("LINE\n"); /*Same line*/
else printf("NONE\n");
}
else{ /*Finding the intersection points*/
X = (b2*c1 - c2*b1)/(a2*b1-b2*a1);
if(b1==0)/*Avoiding division for 0*/
Y = (a2*X+c2)/b2;
else
Y = (a1*X+c1)/b1;
if(Y==0)printf("POINT %.2f 0.00\n",X);
else if(X==0) printf("POINT 0.00 %.2f\n",-Y);
else printf("POINT %.2f %.2f\n",X,-Y);
}
}
printf("END OF OUTPUT");

return 0;
}
``````