Page 1 of 2
10695 - Find the Point
Posted: Thu Aug 05, 2004 11:00 pm
by 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
Hmm
Posted: Fri Aug 06, 2004 12:39 am
by 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...
Re: Hmm
Posted: Fri Aug 06, 2004 6:52 am
by jagadish
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.
hmm
Posted: Fri Aug 06, 2004 7:12 am
by 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
OOOPS
Posted: Fri Aug 06, 2004 8:41 am
by 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
Posted: Fri Aug 06, 2004 8:56 am
by 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
Posted: Fri Aug 06, 2004 9:02 am
by 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
Hmm
Posted: Fri Aug 06, 2004 9:07 am
by 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.
Posted: Fri Aug 06, 2004 3:58 pm
by 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
Posted: Sat Sep 25, 2004 5:27 pm
by 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;
}
Posted: Tue Jan 04, 2005 5:46 pm
by ..
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
Posted: Sat Jan 29, 2005 4:33 pm
by Dreamer#1
..CUT CUT..
Got AC now.
Posted: Sat Jan 29, 2005 6:06 pm
by 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
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~
Posted: Sat Jan 29, 2005 9:12 pm
by 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.
This problem is bugging me
Posted: Mon Apr 18, 2005 7:41 am
by 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?