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

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

Post by Solaris » Tue Jan 03, 2006 6:40 pm

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
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 9:15 pm

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

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Post by stcheung » Mon Jan 16, 2006 6:49 am

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
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Post by stcheung » Mon Jan 16, 2006 7:38 am

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.

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Thu Jun 29, 2006 11:19 am

I am getting crazy :evil:

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

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;
}
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

ldaniele
New poster
Posts: 6
Joined: Sat Aug 12, 2006 2:26 am

378 (Intersecting Lines) WA

Post by ldaniele » Sat Aug 12, 2006 4:08 am

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!

User avatar
Zaspire
New poster
Posts: 36
Joined: Sun Apr 23, 2006 2:42 pm
Location: Russia

Post by Zaspire » Mon Aug 21, 2006 11:27 am

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)

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

whay WA!!

Post by Oronno » Fri Aug 17, 2007 8:20 am

I become tired getting WA from this problem :cry: . 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!!

Last edited by Oronno on Sun Aug 19, 2007 6:28 pm, edited 3 times in total.
I like programming but i am so lazy to do it...

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Aug 17, 2007 9:29 am

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.
Ami ekhono shopno dekhi...
HomePage

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

Post by Oronno » Fri Aug 17, 2007 9:22 pm

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.
:o :roll:

I can't understand whats problem. Plz if can, check my code carefully....
I like programming but i am so lazy to do it...

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Aug 17, 2007 9:49 pm

Code: Select all

if((a1*b2-a2*b1)==0)
Is this check valid? or you should use eps?
Ami ekhono shopno dekhi...
HomePage

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

Post by Oronno » Sat Aug 18, 2007 6:56 pm

I've changed my code as you say, (updated code has posted in previous post), but i am still getting WA!! :cry:
plz check carefully....
I like programming but i am so lazy to do it...

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Aug 19, 2007 2:21 am

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.
Jan wrote:

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
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: whay WA!!

Post by Robert Gerbicz » Sun Aug 19, 2007 12:55 pm

Oronno wrote:I become tired getting WA from this problem :cry: . 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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Aug 19, 2007 1:19 pm

I always add eps before printing a double. Its safe.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 3 (300-399)”