@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
Hello @shilp_adm I have added the requested tag And thanks!!
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
Hello @hrculiz, If you have learnt something new from my text, then it means I am doing things right!! And it’s my pleasure!
Good work bruno, it was painful to watch you struggle with this problem for 2-3 days, but I am really happy for you that you pulled it off, and also hats off to your determination
Thank you very much @v_akshay, your words of motivation also helped me a lot And this problem only proves I need to learn many, many new things like Graphs, DP, Trees… I know it’s a long road, but Im also sure I will get there with time and hard work
Awesome work!! man ,keep it up @kuruma
Thanks @faiz, it’s what I plan to do and I plan to learn lots of new things Thank you very much!
Thank you very much @ravi it’s really wonderful to see that people enjoyed this text And ofc my own personal goal is to keep learning more and more so I can write texts like this for a wider range of problems!! My personal goal now is to work on DP and graphs in a more specfic way and study new data structures so I can implement classic algorithms like LCS, suffix array, etc
Good job @arjunc I have came across that website during contest but actually failed to use the ideas described there and I chose this method instead, so, congratulations