10695 - Find the Point

[nafi]

hi
i have done everything (i guess) to solve this problem (10695). but i'm getting WA. i don't know why. i'm confused.
does anyone have any special test cases?
i print "IMPOSSIBLE" on these cases:
1. if BOC+COA+AOB !=360
2. if !(0<BOC<180) or !(0<COA<180) or !(0<AOB<180)
3. if BOC<=A or COA<=B or AOB<=C

also, i print -0.000000 (if occurs) as 0.000000
can anyone help me
nafi

[shahriar_manzoor]

Often precision error hampers the problem. And the error due to precision error is so high that it cannot just be ignored by special judge.

For example suppose one tangent touches the circle at (10,-23.89999191) and the other at ((10,23.89999191), I mean their abscissa are same but due to precision error you get first value of 10 as 10.0001 and the second one as 10.0000 and so you print the second tangent first but theoritically the first tangent should have been printed first. Believe me that there are approaches which makes the precision errors almost zero. Also with a error prone approach you can employ quantization approach. Quantization is a process related to Numerical Method. Kisman employed quantization when he found that precision error is hampering is results.

My solution assumes the tangent equation to be xcos(alpha)+ysin(alpha)=p. Here for a valid solution p should always be positive...

[jagadish]

Believe me that there are approaches which makes the precision errors almost zero. Also with a error prone approach you can employ quantization approach. Quantization is a process related to Numerical Method.

Sir ,
I have tried solving most of your math-geometrical related problems from the archive but most the time (say 90%) i get WA.. as you said i am sure many people out there are facing the same problem.
Can you please elaborate on these methods and also throw some light on Quantization approach...I am sure it will be of immense help for a LOT of people here.(probably you can make a sticky post on this)

thank you.

[shahriar_manzoor]

Actually my discussion above is only based on this particular problem. You can mail me your code for any one or two other of my geometric problem then I can check what is actually wrong.

Email: shahriar_manzoor@yahoo.com

[shahriar_manzoor]

Sorry,
I gave the above reply based on the problem "Tangent" but now I see that the query was on "Find the Point". This problem has no traps. Only wrong algorithm get cause u wrong answer I think.

I guess I am losing by head

-Shahriar

[nafi]

hi,
thankx for replying, but actually, i asked for the problem #10695 "FIND THE POINT" not tangents. can u give me hint about some tricky tricks?
nafi

[nafi]

i used BISECTION METHOD to solve this problem. i do this to find AO. after that i find BO,CO. then i can easily find the co-ordinates of O. may be the BISECTION cause some precision problems to get me wa. i guess so. or may be this process is wrong! but i don't know!
nafi

[shahriar_manzoor]

The judge solution and alternate solution both are analytical and still the special judge allows some precision errors. You can mail me at the email address above so that I could send u some data.

[nafi]

hi,at last i got it accepted. there was no problem with precision i think. the problem was in my "bisection method". i applied this on AO. but if the angles AOB or AOC was less then 90 then the method becomes useless.
if so occured, i then applied the method on BO or CO. after fixing this, i got ac.
however, it has analytical solution. but i coudn't find any. it may be rather simple.
nafi

[cpmicpmi]

I calculate the coordinates directly,but WA.

Code: Select all

#include <iostream.h>
#include <math.h>
#define Pi 3.141592653589793238462643
int main()
{
   int  x1, y1, x2, y2, x3, y3;
   int d1,d2,d3;
   int M=0;
   double a,b,c,A,B,C,x,y;
   cout.setf(ios::fixed);
   cout.precision(6);
   while(cin>>x1>>y1>>x2>>y2>>x3>>y3 && (!x1||!y1||!x2||!y2||!x3||!y3))
   {
      cin>>d1>>d2>>d3;
      cout<<"Case "<<++M<<":"<<endl;
      if(d1+d2+d3 != 360 || d1>=180 || d1<0 || d2>=180 || d2<0 || d3>=180 || d3<0)
      {
         cout<<"IMPOSSIBLE"<<endl;
         continue;
      }
      a=sqrt((x2-x3)*(x2-x3)+(y2-y3)*(y2-y3));
      b=sqrt((x1-x3)*(x1-x3)+(y1-y3)*(y1-y3));
      c=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
      A=acos((b*b+c*c-a*a)/2/b/c)*180/Pi;
      B=acos((a*a+c*c-b*b)/2/a/c)*180/Pi;
      C=acos((a*a+b*b-c*c)/2/a/b)*180/Pi;
      if(A>=d2 || B>=d3 || C>=d1 )
      {
            cout<<"IMPOSSIBLE"<<endl;
            continue;
      }
      double r1,r2,cx1,cy1,cx2,cy2,dx1=x1-x3,dy1=y1-y3,dx2=x2-x3,dy2=y2-y3,rc,alpha;
      int flag=0;
		
      r1=b/sin(d3*Pi/180)/2;
      r2=a/sin(d2*Pi/180)/2;
      if(dx1*dy2-dx2*dy1>0)
      {
            cx1=(x1+x3)/2.0+sqrt(r1*r1-b*b/4)/b*(dy1);
            //(dx1+i dy1)*(cos(-90)-sin(90)i)
            cy1=(y1+y3)/2.0+sqrt(r1*r1-b*b/4)/b*(-dx1);
            cx2=(x2+x3)/2.0+sqrt(r2*r2-a*a/4)/a*(-dy2);
            //(dx2+i dy2)*(cos(90)+sin(90)i)
            cy2=(y2+y3)/2.0+sqrt(r2*r2-a*a/4)/a*(dx2);
            flag=1;
      }
      else if(dx1*dy2-dx2*dy1<0)
      {
            cx1=(x1+x3)/2.0+sqrt(r1*r1-b*b/4)/b*(-dy1);
            cy1=(y1+y3)/2.0+sqrt(r1*r1-b*b/4)/b*(dx1);
            cx2=(x2+x3)/2.0+sqrt(r2*r2-a*a/4)/a*(dy2);
            cy2=(y2+y3)/2.0+sqrt(r2*r2-a*a/4)/a*(-dx2);
      }
      else
      {
            cout<<"IMPOSSIBLE"<<endl;
            continue;
      }
		
      rc=sqrt((cx1-cx2)*(cx1-cx2)+(cy1-cy2)*(cy1-cy2));
      alpha=acos((r1*r1+rc*rc-r2*r2)/2/r1/rc);
      if(flag)
      {
            x=cx1+r1/rc*((cx2-cx1)*cos(alpha)+(cy2-cy1)*sin(alpha));
            //cos(alpha)-i sin(alpha)
            y=cy1+r1/rc*(-(cx2-cx1)*sin(alpha)+(cy2-cy1)*cos(alpha));
      }
      else
      {
            x=cx1+r1/rc*((cx2-cx1)*cos(alpha)-(cy2-cy1)*sin(alpha));
            //cos(alpha)+i sin(alpha)
            y=cy1+r1/rc*((cx2-cx1)*sin(alpha)+(cy2-cy1)*cos(alpha));
      }
      cout<<x+1e-10<<' '<<y+1e-10<<endl;
   }
   return 0;
}

[..]

Hi cpmicpmi, hope you already solved the problem.
If you still get WA, here is one example

0 0 1 0 185 46
123 67 170

Your program outputs: 1.011225 0.071000
My AC program outputs: 0.949766 0.066631

[Dreamer#1]

..CUT CUT..

Got AC now.

[Observer]

Hi Dreamer#1,

Shouldn't you check your I/O before seeking our help?

Just look at your second case:

Code: Select all

-57 87 -153 183 145 109
120 143 97

And your output

Code: Select all

Case 2:
-49.711801 66.276088

And this point is clearly NOT in the triangle.... hope you see that...

Btw, my accepted program gives

Code: Select all

Case 2:
-54.343876 108.806957

Don't wanna spoil your fun solving this task, so I think I'll stop here~

[Dreamer#1]

oh dear! that was really stupid of me.
I was so worried about the precision error that I didn't even notice such a huge bug.

Observer bro thanks a lot for your sharp observervation.
Got AC now.

To people who is getting WA in this problem and ended up reading the previous posts in this thread, precision is most probably not why you are getting WA so give more attention to the correctness of your solution and worry less about the precision.

[jaredjohnson]

I have a solution that works for all of the input I have seen, but I don't think it works if any of the three angles == 180 degrees, does this work on any of your A/C programs?