Editorial for TLE '16 Contest 3 P2 - In Remembrance


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: ZQFMGB12

This is another simple implementation problem. In order to check if a point (xi,yi) is on the polynomial, all we have to do is check if f(xi) is equal to yi. In order to check if a point (xi,yi) is within the ending explosion, we need to find the ending point, which is located at (V,f(V)), and use the Euclidean distance formula to determine if the distance between (xi,yi) and (V,f(V)) is less than or equal to R. In order to quickly determine values of f(x), we can pre-compute all values of f(x) from 0 to V, but this is not necessary to pass.

However, there are some important corner cases to check. The first is that we should not evaluate f(x) if x>V 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: O(N+VP)


Comments

There are no comments at the moment.