10695  Find the Point
Moderator: Board moderators
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
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

 System administrator & Problemsetter
 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...
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...
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 mathgeometrical 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.

 System administrator & Problemsetter
 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
Email: shahriar_manzoor@yahoo.com

 System administrator & Problemsetter
 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
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

 System administrator & Problemsetter
 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.
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
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
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((x2x3)*(x2x3)+(y2y3)*(y2y3));
b=sqrt((x1x3)*(x1x3)+(y1y3)*(y1y3));
c=sqrt((x1x2)*(x1x2)+(y1y2)*(y1y2));
A=acos((b*b+c*ca*a)/2/b/c)*180/Pi;
B=acos((a*a+c*cb*b)/2/a/c)*180/Pi;
C=acos((a*a+b*bc*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=x1x3,dy1=y1y3,dx2=x2x3,dy2=y2y3,rc,alpha;
int flag=0;
r1=b/sin(d3*Pi/180)/2;
r2=a/sin(d2*Pi/180)/2;
if(dx1*dy2dx2*dy1>0)
{
cx1=(x1+x3)/2.0+sqrt(r1*r1b*b/4)/b*(dy1);
//(dx1+i dy1)*(cos(90)sin(90)i)
cy1=(y1+y3)/2.0+sqrt(r1*r1b*b/4)/b*(dx1);
cx2=(x2+x3)/2.0+sqrt(r2*r2a*a/4)/a*(dy2);
//(dx2+i dy2)*(cos(90)+sin(90)i)
cy2=(y2+y3)/2.0+sqrt(r2*r2a*a/4)/a*(dx2);
flag=1;
}
else if(dx1*dy2dx2*dy1<0)
{
cx1=(x1+x3)/2.0+sqrt(r1*r1b*b/4)/b*(dy1);
cy1=(y1+y3)/2.0+sqrt(r1*r1b*b/4)/b*(dx1);
cx2=(x2+x3)/2.0+sqrt(r2*r2a*a/4)/a*(dy2);
cy2=(y2+y3)/2.0+sqrt(r2*r2a*a/4)/a*(dx2);
}
else
{
cout<<"IMPOSSIBLE"<<endl;
continue;
}
rc=sqrt((cx1cx2)*(cx1cx2)+(cy1cy2)*(cy1cy2));
alpha=acos((r1*r1+rc*rcr2*r2)/2/r1/rc);
if(flag)
{
x=cx1+r1/rc*((cx2cx1)*cos(alpha)+(cy2cy1)*sin(alpha));
//cos(alpha)i sin(alpha)
y=cy1+r1/rc*((cx2cx1)*sin(alpha)+(cy2cy1)*cos(alpha));
}
else
{
x=cx1+r1/rc*((cx2cx1)*cos(alpha)(cy2cy1)*sin(alpha));
//cos(alpha)+i sin(alpha)
y=cy1+r1/rc*((cx2cx1)*sin(alpha)+(cy2cy1)*cos(alpha));
}
cout<<x+1e10<<' '<<y+1e10<<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
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.
Hi Dreamer#1,
Shouldn't you check your I/O before seeking our help?
Just look at your second case:
And your output
And this point is clearly NOT in the triangle.... hope you see that...
Btw, my accepted program gives
Don't wanna spoil your fun solving this task, so I think I'll stop here~
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
Btw, my accepted program gives
Code: Select all
Case 2:
54.343876 108.806957
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
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.
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.

 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?