Page **2** of **4**

Posted: **Tue Jan 03, 2006 6:40 pm**

by **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

Posted: **Tue Jan 03, 2006 9:15 pm**

by **mamun**

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

Posted: **Mon Jan 16, 2006 6:49 am**

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

Posted: **Mon Jan 16, 2006 7:38 am**

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

Posted: **Thu Jun 29, 2006 11:19 am**

by **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;
}
```

### 378 (Intersecting Lines) WA

Posted: **Sat Aug 12, 2006 4:08 am**

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

Posted: **Mon Aug 21, 2006 11:27 am**

by **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)

### whay WA!!

Posted: **Fri Aug 17, 2007 8:20 am**

by **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!!
```

Posted: **Fri Aug 17, 2007 9:29 am**

by **Jan**

Check this line.

What if a2=0? So, better to use

Hope it helps.

Posted: **Fri Aug 17, 2007 9:22 pm**

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

Posted: **Fri Aug 17, 2007 9:49 pm**

by **Jan**

Is this check valid? or you should use eps?

Posted: **Sat Aug 18, 2007 6:56 pm**

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

Posted: **Sun Aug 19, 2007 2:21 am**

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

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

### Re: whay WA!!

Posted: **Sun Aug 19, 2007 12:55 pm**

by **Robert Gerbicz**

Oronno wrote: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:

, 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);

Posted: **Sun Aug 19, 2007 1:19 pm**

by **Jan**

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