Page 2 of 4
Posted: 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

Posted: Tue Jan 03, 2006 9:15 pm
Thank you Solaris. My program failed in the first case.

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

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

Posted: Thu Jun 29, 2006 11:19 am
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
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
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
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
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.

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

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

Posted: 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?

Posted: 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!!
plz check carefully....

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

### Re: whay WA!!

Posted: Sun Aug 19, 2007 12:55 pm
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:

Code: Select all

``````1
1 0 1 1 2 0 2 1
``````
, because your program outputs LINE, however the correct answer is NONE.