10695 - Find the Point

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

nafi
New poster
Posts: 11
Joined: Sat Jul 31, 2004 10:35 pm
Location: Dhaka, Bangladesh
Contact:

10695 - Find the Point

Post by nafi » Thu Aug 05, 2004 11:00 pm

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
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Hmm

Post by shahriar_manzoor » Fri Aug 06, 2004 12:39 am

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
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Re: Hmm

Post by jagadish » Fri Aug 06, 2004 6:52 am

shahriar_manzoor wrote: 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
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Fri Aug 06, 2004 7:12 am

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
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

OOOPS

Post by shahriar_manzoor » Fri Aug 06, 2004 8:41 am

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
New poster
Posts: 11
Joined: Sat Jul 31, 2004 10:35 pm
Location: Dhaka, Bangladesh
Contact:

Post by nafi » Fri Aug 06, 2004 8:56 am

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
New poster
Posts: 11
Joined: Sat Jul 31, 2004 10:35 pm
Location: Dhaka, Bangladesh
Contact:

Post by nafi » Fri Aug 06, 2004 9:02 am

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
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Hmm

Post by shahriar_manzoor » Fri Aug 06, 2004 9:07 am

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
New poster
Posts: 11
Joined: Sat Jul 31, 2004 10:35 pm
Location: Dhaka, Bangladesh
Contact:

Post by nafi » Fri Aug 06, 2004 3:58 pm

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
New poster
Posts: 3
Joined: Thu Oct 09, 2003 2:41 pm

Post by cpmicpmi » Sat Sep 25, 2004 5:27 pm

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;
}

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Tue Jan 04, 2005 5:46 pm

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
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 » Sat Jan 29, 2005 4:33 pm

..CUT CUT..

Got AC now.
Last edited by Dreamer#1 on Sat Jan 29, 2005 9:13 pm, edited 1 time in total.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sat Jan 29, 2005 6:06 pm

Hi Dreamer#1,

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

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~ 8)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 » Sat Jan 29, 2005 9:12 pm

oh dear! that was really stupid of me. :oops:
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. :D
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
New poster
Posts: 11
Joined: Sun Jan 30, 2005 10:21 pm

This problem is bugging me

Post by jaredjohnson » Mon Apr 18, 2005 7:41 am

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?

Post Reply

Return to “Volume 106 (10600-10699)”