TLE '16 Contest 3 P2 - In Remembrance

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 3.0s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Fax McClad beside his powerful space cannon.

Once a year, all creatures in the Lylot System, big and small, take some time off in order to remember the great sacrifices that soldiers have made in order to keep the Lylot System safe from evils such as the Space Pirates and the Dankey Kang Gang. In the Lylot System, this day is called "Remembrance Day."

Today, Fax is in charge of firing a large space cannon as part of the Remembrance Day ceremony. However, he needs to make sure that no planets are in danger. In particular, there are P planets that he needs to be aware of; the i^{th} planet is located at (x_i,y_i). No two planets will be located at the same point or at (0,0). The space cannon is located at (0,0) and does not count as a planet.

The cannon projectile's path can be modeled using an N^{th} degree polynomial f(x) = a_1x^N + a_2x^{N-1} + \dots + a_Nx. Additionally, when the cannon projectile's x coordinate reaches a certain value V, the projectile explodes and ceases to exist. The explosion is in the shape of a circle with a radius of R.

Fax needs to ensure that no planet is on the path of the cannon projectile and that no planet is caught in the final explosion area, even at the edge. Can you help Fax to determine how many planets are in danger?

Input Specification

The first line of input will contain four space-separated integers, P (1 \leq P \leq 100\,000), N (1 \leq N \leq 10), V (0 \leq V \leq 1\,000), and R (0 \leq R \leq 2\,000).

P lines of input follow. The i^{th} line will contain two space-separated integers x_i (0 \leq x_i \leq 2\,000) and y_i (-10^8 \leq y_i \leq 10^8), the coordinates of the i^{th} planet.

N lines of input follow. The j^{th} line will contain a single integer, a_j (-2 \cdot 10^9 \leq a_j \leq 2 \cdot 10^9). It is guaranteed that in the interval [0,V] (that is, from 0 to V, inclusive), the absolute value of f(x) will not exceed 10^8.

Output Specification

On a single line, output the number of planets in the path of the cannon projectile or in the explosion area.

Sample Input

6 3 5 2
1 1
2 0
3 3
5 2
6 1
4 -5

Sample Output


Explanation for Sample Output

In the diagram, the blue curve represents the cannon projectile's path, the red circle represents the explosion area, and the black points represent the locations of planets. The planets located at (2,0), (5,2), and (6,1) are in danger.

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported


There are no comments at the moment.