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
@bruno: good work man, keep it up
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
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 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