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

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

Thanks everyone

Post by Oronno » Sun Aug 19, 2007 6:23 pm

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!! :lol:
I like programming but i am so lazy to do it...

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

Post by AcmNightivy » Tue Dec 04, 2007 10:31 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``

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

Post by Oronno » Tue Dec 04, 2007 9:10 pm

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

Post by AcmNightivy » Wed Dec 05, 2007 2:41 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.

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

Post by Oronno » Wed Dec 05, 2007 7:12 am

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

Post by AcmNightivy » Wed Dec 05, 2007 11:14 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..
And my answer is:
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

Post by AcmNightivy » Wed Dec 05, 2007 1:07 pm

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

Post by AcmNightivy » Sun Dec 09, 2007 7:15 am

help..

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

Post by AcmNightivy » Tue Dec 11, 2007 3:11 pm

it has puzzled me for 2 weeks...help!

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

Post by AcmNightivy » Sun Dec 16, 2007 2:25 pm

really i can't find the mistake...
three weeks...

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

Wa

Post by Mata » Sat Jan 26, 2008 1:58 am

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;
}
/********************************
********************************/

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

378

Post by linux » Sun Jan 27, 2008 11:28 am

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

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

378

Post by linux » Sun Jan 27, 2008 11:33 am

AcmNightivy wrote:

Code: Select all

         else   //k1,k2 all exist,find point 
         { 
            k1 = returnK(tasks.p1,tasks.p2); 
            k2 = returnK(tasks.p3,tasks.p4); 
            b1 = returnB(tasks.p1,k1); 
            b2 = returnB(tasks.p3,k2); 
            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

Post by AcmNightivy » Fri Feb 01, 2008 1:30 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

Post by Rafa3p » Thu Dec 29, 2011 3:37 am

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;
}
Please give me some help.

Post Reply

Return to “Volume 3 (300-399)”