## 10695 - Find the Point

Moderator: Board moderators

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

### 10695 - Find the Point

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

### Hmm

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

Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

### Re: Hmm

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

### hmm

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

### OOOPS

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

### Hmm

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
Contact:
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
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
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

My AC program outputs: 0.949766 0.066631
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 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
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``````

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

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm
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
New poster
Posts: 11
Joined: Sun Jan 30, 2005 10:21 pm

### This problem is bugging me

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?