378 - Intersecting Lines

[Solaris]

It is one of my earlier codes. Seeing my code I could get the following hints :

1. Check for the lines that are parallel to Y axis (slope = inf)
2. Check for the lines that are parallel to Y axis and have the same X co-ord
3. Check for the liens that have the same slope

• a. Whether they meet on line
  b. Whether they meet on point

[mamun]

Thank you Solaris. My program failed in the first case.

[stcheung]

roticv, thanks for the sample input. Can you (or anyone else) provide the AC output for those? Too lazy to run those manually...thanks very much.

[stcheung]

Okay I got AC after using "long double" for slope, y-intercept etc instead of just double...sigh it's one of those problems again.

[Kallol]

I am getting crazy

what is the problem with my code?? It passed all sample tests I found here . Still getting WA .

Can anyone help me?????

here is my code ..

Code: Select all

#include<stdio.h>
#include<math.h>

int main(void)
{
	register long double x1,y1,x2,y2,x3,y3,x4,y4,a1,b1,c1,a2,b2,c2,l,xh,yh,x,y;
	register int test;
	scanf("%d",&test);
	printf("INTERSECTING LINES OUTPUT\n");
	while(test--)
	{
		scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);

		a1=y1-y2;
		b1=x2-x1;
		c1=y1*(x1-x2)-x1*(y1-y2);

		a2=y3-y4;
		b2=x4-x3;
		c2=y3*(x3-x4)-x3*(y3-y4);

		if((c1==0 && c2==0))
		{
			if(a2!=0 && b2!=0 )
			{
				if((fabs((a1/a2)-(b1/b2)))>0.00)
				{
					printf("POINT 0.00 0.00\n");
					continue;
				}
				else
				{
					printf("LINE\n");
					continue;
				}
			}
			else
			{
				if(a1!=0 && a2==0.0)
				{
					printf("POINT 0.00 0.00\n");
					continue;
				}
				if(b1!=0 && b2==0.0)
				{
					printf("POINT 0.00 0.00\n");
					continue;
				}
			}
		}
		if(a1==0 && a2==0)
		{
			if(fabs((c1/b1)-(c2/b2))<0.000000000000000000000000001)
			{
				printf("LINE\n");
			}
			else
			{
				printf("NONE\n");
			}
			continue;
		}
		if(b1==0 && b2==0)
		{
			if(fabs((c1/a1)-(c2/a2))<0.0000000000000000000000000001)
			{
				printf("LINE\n");
			}
			else
			{
				printf("NONE\n");
			}
			continue;
		}
		
		if(a1==0 && c1==0)
		{
			y=0;
			x=-c2/a2;
			printf("POINT %.2lf %.2lf\n",x,y);
			continue;
		}
		if(a2==0 && c2==0)
		{
			y=0;
			x=-c1/a1;
			printf("POINT %.2lf %.2lf\n",x,y);
			continue;
		}
		if(b1==0 && c1==0)
		{
			x=0;
			y=-c2/b2;
			printf("POINT %.2lf %.2lf\n",x,y);
			continue;
		}
		if(b2==0 && c2==0)
		{
			x=0;
			y=-c1/b1;
			printf("POINT %.2lf %.2lf\n",x,y);
			continue;
		}

		
		
		
		if(b1!=0.0 && b2!=0.0 && fabs((a1/b1)-(a2/b2))<.00000000000000000000000000001)
		{
			if(fabs((a1/a2)-(c1/c2))<.0000000000000000000000000000001 && fabs((b1/b2)-(c1/c2))<.0000000000000000000000000000001)
			{
				printf("LINE\n");
			}
			else
			{
				printf("NONE\n");
			}
		}
		else
		{
			l=a2*b1 - a1*b2;
			xh= b2*c1 - b1*c2;
			yh= a1*c2 - a2*c1;

			x= xh/l;
			y= yh/l;

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

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

[ldaniele]

Hallo to everybody,
first of all sorry for my english!!!
Can anyone help me understanding what's wrong in my program
Here's the code

#include<iostream>
#include<stdio.h>
#include<iomanip>

//#define PROVA
#ifdef PROVA

#include<fstream>
using std::ofstream;
using std::ifstream;
using std::setprecision;
using std::cout;
//ofstream cout("output.txt");
ifstream cin("input.txt");

#endif
#ifndef PROVA

using std::cin;
using std::cout;

#endif

class Punto{
public: double x, y;
Punto(){}
Punto(double x, double y)(x), y(y){}
bool operator<(const Punto& punto) const {//definizione utile per la risoluzione del problema
return this->y<punto.y;
}
};

class Line{
public: Punto p1, p2;
Line(Punto p1, Punto p2):p1(p1), p2(p2) {}

};


//trova il punto di intersezione delle rette dedotte dalle due linee risolvendo il sistema ottenuto
//e poi verifica che tale punto cada all'interno degli intervalli dei due segmenti
inline void intersected(Line line1, Line line2){
Punto p1=line1.p1, p2=line1.p2, p3=line2.p1, p4=line2.p2;
//formula given by the resolution of the system of two equations in two unknowns where the equation of
//one rect that pass through p1 and p2 is: (x -x1)/(x2-x1)=(y-y1)/(y2-y1)
// so we gave the x=num/den coordinate of the point of intersection
double num =(p1.x)*(p2.y - p1.y)*(p4.x - p3.x) - (p1.y)*(p2.x - p1.x)*(p4.x - p3.x) - (p3.x)*(p4.y - p3.y)*(p2.x - p1.x) + (p3.y)*(p2.x - p1.x)*(p4.x - p3.x);
double den =(p2.y - p1.y)*(p4.x - p3.x) - (p4.y - p3.y)*(p2.x -p1.x);
//cout<<"num "<<num<<" den "<<den<<" -- ";
if(den==0){//they are parallel
//test if the point of one line(line2) belong to the other line(line1)->the are overlapped
if( (p3.x-p1.x)*(p2.y-p1.y) == (p3.y-p1.y)*(p2.x-p1.x) )//formula della retta per p1 e p2 (line1) alle cui incognite si sono sostituite le coordinate di p3 (estreamo di line2)
printf("LINE\n"); //caso 1
else printf("NONE\n"); //caso 2
return;
}
double x=num/den;
if(num==-0) x=0;
double den2=(p4.x - p3.x);
double y=0;
//this is to avoid the risk of having a null denominator
if(den2!=0)
y=(x - p3.x)*(p4.y - p3.y)/den2 + p3.y;
else
y=(x - p1.x)*(p2.y - p1.y)/(p2.x-p1.x) + p1.y;
//cout<<"x "<<x<<" y "<<y<<" --" ;
printf("POINT %4.2f %.4.2f\n",x,y); //caso 3
}


main(){
int caseNum=0;
cin>>caseNum;
printf("INTERSECTING LINES OUTPUT\n");
for(;caseNum>0;caseNum--){
Punto p1,p2,p3,p4;
cin>>p1.x>>p1.y>>p2.x>>p2.y>>p3.x>>p3.y>>p4.x>>p4.y;
Line line1(p1,p2), line2(p3,p4);
intersected(line1,line2);
}
printf("END OF OUTPUT\n");
}

N.B:defining PROVA it read from input.txt and write on standard output!

I tested it with many cases and formulas are correct; i think it is incorrect with particular input, so i will be very happy if someone (an admin) could post which is (are) the input that generate a wrong answer.
Thanks!

[Zaspire]

May be you need some correct in you code:
int x1,y1,x2,y2,x3,y3,x4,y4
if(fabs((c1/b1)-(c2/b2))<0.001)

[Oronno]

I become tired getting WA from this problem . I test all the SAMPLE I/o from forum, my program show Correct Answer. But whats happen to UVA???
plz help....if can give some sample I/O for which my code show WA

Code: Select all

//CODE has removed after getting AC!!

[Jan]

Check this line.

Code: Select all

if(fabs((a1/a2)-(b1/b2))<esp

What if a2=0? So, better to use

Code: Select all

if(fabs((a1*b2)-(b1*a2))<esp

Hope it helps.

[Oronno]

Hmm...You catch a good part for which someone might get WA.
But after solving this, i am getting WA again.
only the improvement is that, before doing this correction, ACM says-

Your program has not solved the problem. It ran during 0.002 seconds.

& after correction it show-

Your program has not solved the problem. It ran during 0.000 seconds.

I can't understand whats problem. Plz if can, check my code carefully....

[Jan]

Code: Select all

if((a1*b2-a2*b1)==0)

Is this check valid? or you should use eps?

[Oronno]

I've changed my code as you say, (updated code has posted in previous post), but i am still getting WA!!
plz check carefully....

[mf]

Code: Select all

      if(fabs(a1*b2-a2*b1)<eps)
      {
         if(fabs(a1*b2-a2*b1)<eps && fabs(b1*c2-b2*c1)<eps)
            printf("LINE\n"); 

Look for a bug in this part of your code - why did you use a1*b2-a2*b1 twice.

Code: Select all

if((a1*b2-a2*b1)==0)

Is this check valid? or you should use eps?

That shouldn't matter because inputs are all integers, and so all computations will be exact.

[Robert Gerbicz]

I become tired getting WA from this problem . I test all the SAMPLE I/o from forum, my program show Correct Answer. But whats happen to UVA???
plz help....if can give some sample I/O for which my code show WA

Your code fails on the following test:

Code: Select all

1
1 0 1 1 2 0 2 1

, because your program outputs LINE, however the correct answer is NONE.
Think about why your code is wrong.
And don't add eps for the final output. It is a rare case on ACM uva, that you need that to avoid precision problems, just use:
printf("POINT %.2lf %.2lf\n",x,y);

[Jan]

I always add eps before printing a double. Its safe.