Editorial for TLE '16 Contest 3 P2 - In Remembrance
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
This is another simple implementation problem. In order to check if a point is on the polynomial, all we have to do is check if
is equal to
. In order to check if a point
is within the ending explosion, we need to find the ending point, which is located at
, and use the Euclidean distance formula to determine if the distance between
and
is less than or equal to
. In order to quickly determine values of
, we can pre-compute all values of
from
to
, but this is not necessary to pass.
However, there are some important corner cases to check. The first is that we should not evaluate if
since the point could not possibly be on the polynomial. Next, we need to make sure that a point that is on the polynomial and within the explosion is not counted twice. Additionally, one should use either floating point numbers or 64-bit integers to compute distances.
Time Complexity:
Comments