@kuruma : I did this problem without any floating point computations . The approach was similarly based on determinants . You may like to have a look at my solution : CodeChef: Practical coding for everyone .
Hi, instead of finding the parameters of the circumcircle of a triangle, you can directly find whether three points form a unique circle or not in the following way:
Equation of a circle (expanded):
x^2 + y^2 + gx + fy + c = 0
After substituting the three points (xi,yi) in the above equation we get three linear equations in g,f and c. If they have a unique solution, then following determinant is not 0 and there exists a unique circle which passes through the three points (xi,yi) :
| x1 y1 1 |
| x2 y2 1 |
| x3 y3 1 |
If indeed it is not 0, then you can find the values of g,f and c by Cramer’s rule. Now you have all the parameters required for the equation of the circle.
Finally to check if a point (x_ash,y_ash) lies inside or on the circle check if p(x) <= 0 (use an epsilon value)
p(x) = x^2 + y^2 + gx + fy + c
P.S. p(x) = 0 when point lies on the circle and p(x) > 0 when point lies outside the circle
My solution implements this idea : CodeChef: Practical coding for everyone
We dont need any floating point calculation:
for each possible 4 points do the following
.
|x1 y1 1 |
|x2 y2 1 | = D1
|x3 y3 1 |
.
if the determinant is 0 the points are collinear, so quit.
else the sign of the determinant tells you if they are arranged CW/anti-CW
Now check the determinant
.
|x1 y1 x1*x1+y1*y1 1|
|x2 y2 x2*x2+y2*y2 1|
|x3 y3 x3*x3+y3*y3 1| = D2
|x4 y3 x4*x4+y4*y4 1|
.
if D1*D2<=0 then the agent is killed.
see my implementation here
Great work kuruma! I’ve always felt you try to give your very best to this CodeChef community. Keep it up!
I did this problem by almost exactly the same concept as described above by kriateive and it turned out to be a rather simple approach. It uses the final result of the long geometrical proof as described in the official editorial.
Learned new approaches from your Work, thank you for your work
I starting solving this problem using the properties of triangle, concept of circum-circle then I ended up with the equation of circle using 3 points.
Here is my approach
@bruno: good work man, keep it up
This solution looks good.
I would like to show my approach.
Equn. of circle passing through 3 points using System of Circles:
When P(x1, y1), Q(x2, y2) and R(x3, y3) are the points:
Equn. of PQ: L: (y-y2 / x-x2) - (y1-y2 / x1-x2) = 0
Equn of Circle with PQ as diameter: C: (x-x1)(x-x2) + (y-y1)(y-y2) = 0
System of circles through the intersection of C and L:
C + kL = 0
=> k = -C/L (if L equals 0 then k = C)
substitute R in C and L to get k.
Now, you get the equation of Circle as C + kL = 0
For any other value D(x, y) (call this guy Ash).
put D in C + kL = 0
if the value is negative (inside the circle) or zero (on the circle) Ash gets killed.
For this approach, we need 4 points P, Q, R => Team Rocket, D => Ash
For each P, Q, R iterate D (find positions for Ash that gets him killed).
Got this idea form here http://www.qc.edu.hk/math/Advanced%20Level/circle%20given%203%20points.htm (method 5).
Let me know your thoughts
Good Work! You should remove the tag “jul13”, which will be removed anyways by the admins some time later. The tag is reserved for editorials.
I think that the tag jul13 is reserved for all questions related to the contest… But, I can also easily remove it
I can recognize some mathematical expressions there very similar to the ones I have used yes It seems you also used the 3 points of the triangle and possibly exploited some mathematical and/or geometrical facts that I haven’t used! Nontheless, thanks for showing me a solution without any divisions I was curious during contest to see how this was done and now I know
@vineetpaliwal : I saw your solution and I myself employed a similar kind of approach but the center coordinates were being computed differently if the order of points was changed.
Hello @sanchit_h, Yes, after contest I was also told that general equation of circle could be used in the solution, but, I couldnt remember Cramer’s rule at the time So I ended up using this more geometric approach :(( I still have much, much to learn… That’s why I am here for Thanks for you explanation!
That’s what I did. Great & simple approach, isn’t it?
@kuruma Awesome work . Really appreciate your time and dedication to help fellow coders. Keep up the good work buddy !!
@ani94, As I said before, it’s really a pleasure to be able to learn and grow up as a coder with this community and I hope I can stick around for many years to come
@vpyati, Thank you very much!! It means a lot to me that people appreciate my work here as a member of Codechef community and if I managed to inspire at least one person with my work, then I am really, really happy!!
Thank you very much @i_wanna_rokk, I always try to give my best in everything and if its something I love, like Algorithms, even more
But, above all I am here to learn
Best regards,
Bruno
Hello @hrculiz, If you have learnt something new from my text, then it means I am doing things right!! And it’s my pleasure!