378 - Intersecting Lines

[Oronno]

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

[AcmNightivy]

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]

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

[AcmNightivy]

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.

[Oronno]

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

[AcmNightivy]

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]

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]

help..

[AcmNightivy]

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

[AcmNightivy]

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

[Mata]

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]

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.

[linux]

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
}

[AcmNightivy]

Thanks~linux
Let me try~Maybe it is the problem exist~Thanks~

[Rafa3p]

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.