CIRKILL - Non-official editorial describing my approach

Nice one kuruma!

I will add the official editorial shortly! I request you to tag your editorial with the “july13” tag (it is “jul13”) right now, so that everyones able to find it.

I have to refer to this post :smiley:

1 Like

@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 : http://www.codechef.com/viewsolution/2317309 .

1 Like

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 : http://www.codechef.com/viewsolution/2340376

2 Likes

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

5 Likes

@Kuruma I really appreciate your passion. Its truly inspiring !!

1 Like

Great work kuruma! I’ve always felt you try to give your very best to this CodeChef community. Keep it up! :slight_smile:

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.

1 Like

Learned new approaches from your Work, thank you for your work :slight_smile:
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

1 Like

@bruno: good work man, keep it up :slight_smile:

1 Like

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 :slight_smile:

1 Like

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 :slight_smile:

Hello @shilp_adm I have added the requested tag :smiley: And thanks!!

I can recognize some mathematical expressions there very similar to the ones I have used yes :slight_smile: 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 :smiley: 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 :frowning: So I ended up using this more geometric approach :(( I still have much, much to learn… That’s why I am here for :slight_smile: Thanks for you explanation!

1 Like

That’s what I did. Great & simple approach, isn’t it? :slight_smile:

@kuruma Awesome work . Really appreciate your time and dedication to help fellow coders. Keep up the good work buddy !!

2 Likes

@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 :slight_smile:

1 Like

@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!! :slight_smile:

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 :slight_smile:

But, above all I am here to learn :smiley:

Best regards,
Bruno