378 - Intersecting Lines

[mamun]

I passed the samples I/O given in the threads. Still getting WA. Can anybody send many more? Thanks in advance.

[mamun]

Nothing? Well, I give here some random input. Can sombody post his accepted output.

Code: Select all

30
106 860 288 -920 573 158 -58 -730
660 151 349 998 302 577 715 551
478 975 439 720 -483 -747 120 -209
-836 839 -889 596 -803 -49 -249 447
-552 -963 538 68 -929 512 23 -875
861 157 611 385 382 693 189 846
286 690 591 476 408 -547 188 -337
520 -173 99 -828 -862 304 -35 -813
293 -428 -762 359 -72 -347 -192 113
-255 -363 -95 -294 -724 83 443 318
842 852 -372 39 729 -818 770 627
162 606 -499 -58 -104 636 227 -236
-859 49 896 -744 844 270 813 -209
996 190 364 -300 -796 978 353 -353
-925 -506 967 -609 537 -419 367 94
166 808 -901 -110 -248 527 -947 355
278 -121 374 674 587 388 -634 -426
739 -559 477 480 -565 110 290 -840
-814 196 62 887 -425 706 -975 252
436 948 615 -312 509 960 -819 309
81 440 133 -101 142 309 903 528
638 888 -995 -410 498 -714 128 170
287 968 843 75 -483 537 -92 114
-377 696 452 -489 605 417 966 -736
296 301 -607 -475 851 140 369 778
347 98 978 166 561 520 240 229
625 366 -995 -873 304 270 -717 194
893 223 -722 -967 752 880 11 775
452 498 733 -748 556 489 278 941
-20 609 -988 324 -221 -761 498 -406


(They are really random. Seems all are intersecting)

[mamun]

Somebody post their output please.

[Solaris]

My AC code gives the following o/p ... hope this helps

INTERSECTING LINES OUTPUT
POINT 227.49 -328.23
POINT 508.35 564.01
POINT 324.87 -26.21
POINT -1084.68 -301.19
POINT -166.73 -598.58
POINT -449.44 1352.12
POINT -4144.68 3798.74
POINT 41.89 -916.85
POINT -133.96 -109.50
POINT 2095.99 650.86
POINT 775.11 807.21
POINT -22.33 420.84
POINT 781.72 -692.36
POINT 330.00 -326.36
POINT 593.22 -588.65
POINT -125.60 557.12
POINT 317.79 208.53
POINT 1012.21 -1642.46
POINT -5969.27 -3870.54
POINT 439.16 925.76
POINT 94.89 295.44
POINT 29.82 404.58
POINT 2697.99 -2904.33
POINT 1242.42 -1618.85
POINT 558.77 526.81
POINT 61.56 67.24
POINT 520.56 286.12
POINT 2030.51 1061.17
POINT 394.99 750.78
POINT 6355.47 2486.08
END OF OUTPUT

[mamun]

Thanks Solaris.
I also get the same. So where can be the trick?

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

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